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 Sam K., 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

More Recursion practice problems

See all Recursion problems →