Permutations II Medium 0 attempts
LeetCode ↗

Permutations II

Medium BacktrackingRecursion LeetCode

You're given an array nums that may contain repeated values. Generate every distinct permutation of its elements, in any order.

The tricky part is filtering out duplicate arrangements. For instance, when two 1s exist in the input, swapping those two shouldn't be treated as producing a separate permutation.

Input Format
Implement permuteUnique(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
nums = [1,1]
Output
[[1,1]]
Constraints
  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10
Test Cases (2)
Case 1
Args: [[1,1,2]] Expected: [[1,1,2],[1,2,1],[2,1,1]]
Case 2
Args: [[1,1]] Expected: [[1,1]]
Topics
BacktrackingRecursion

Build a frequency map of each number. At each recursive step, pick a number that still has remaining count, decrement it, and recurse. This naturally avoids duplicates since you never place the same value at the same position twice.

javascript
function permuteUnique(nums) {
  const result = [];
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);

  function backtrack(path) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (const [num, count] of freq) {
      if (count === 0) continue;
      freq.set(num, count - 1);
      path.push(num);
      backtrack(path);
      path.pop();
      freq.set(num, count);
    }
  }

  backtrack([]);
  return result;
}

Time: O(n! * n) — at most n! permutations, each taking O(n) to copy. Space: O(n) for the recursion stack and frequency map.

Saved in this browser only. Private to you.

JavaScript