Permutations II Medium 0 attempts
LeetCode ↗

Permutations II

Medium BacktrackingRecursion LeetCode

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

The key challenge is avoiding duplicate permutations. For example, if the input has two 1s, swapping them shouldn't produce a new permutation.

Examples

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

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

Constraints

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10
Sample Input
nums = [1,1,2]
Sample Output
[[1,1,2],[1,2,1],[2,1,1]]
Constraints
  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10
Test Cases
Case 1
Args: [[1,1,2]] Expected: [[1,1,2],[1,2,1],[2,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.

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