Skip to main content

47. Permutations II

medium

Generate every unique permutation when the input may contain duplicates. Tests whether you can prune duplicate branches at the right place — a classic 'sort + skip duplicates by index' pattern.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Constraints

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

Examples

Example 1

Input
nums = [1,1,2]
Output
[[1,1,2],[1,2,1],[2,1,1]]

Example 2

Input
nums = [1,2,3]
Output
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Sort nums first so that duplicates are adjacent in the original array.

Hint 2

Same backtracking skeleton as Permutations with a used[] array — but add one prune rule.

Hint 3

Skip nums[i] if i > 0 and nums[i] == nums[i-1] and !used[i-1] — the !used[i-1] is the trick: we only pick the first occurrence first in any given branch.

Hint 4

Note: the rule used[i-1] vs !used[i-1] both work; !used[i-1] is the more conventional one and prunes earlier.

Solution approach

Reveal approach

Sort nums in place. Use the standard backtracking template with a path array and a used boolean array. At each depth, loop i over nums.indices and apply two prune rules: (1) skip if used[i] (the value at index i is already in the current path), (2) skip if i > 0 and nums[i] == nums[i-1] and !used[i-1] — this prunes the second branch that would produce the same path as the first. The 'used[i-1] is false' phrasing means we only allow consuming a duplicate after its earlier copy is already used in the current path. Time is O(n * n!) worst case; the prune brings it down toward unique-permutation count.

Complexity

Time
O(n * n!)
Space
O(n)

Related patterns

  • backtracking
  • recursion
  • duplicates-handling

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Permutations II and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →