The problem. Given a collection of numbers nums that might contain duplicates, return all unique permutations in any order.
nums = [1, 1, 2] -> [[1,1,2], [1,2,1], [2,1,1]]
nums = [1, 2, 3] -> all 6 permutations
nums = [2, 2, 2] -> [[2,2,2]]Duplicates appear because the two 1s can swap places and still give the same list. Fix that by agreeing to use equal values in their sorted order: sort the array, and allow nums[i] only if it differs from nums[i − 1] or nums[i − 1] is already used. The check is if (i > 0 && nums[i] === nums[i − 1] && !used[i − 1]) continue. Then among equal values, the first unused one is always the one placed — every distinct permutation is built exactly once.
function permuteUnique(nums) { const seen = new Set(); const result = []; const used = new Array(nums.length).fill(false); const path = []; const build = () => { if (path.length === nums.length) { const key = path.join(","); if (!seen.has(key)) { // keep only the first copy of each seen.add(key); result.push([...path]); } return; } for (let i = 0; i < nums.length; i++) { if (used[i]) continue; used[i] = true; path.push(nums[i]); build(); path.pop(); used[i] = false; } }; build(); return result;}Time O(n · n!), space O(n · n!) for the set. With many duplicates it builds far more than it keeps — [1,1,1,1,1,1,1,2] makes 40,320 lists to keep 8.
A value equal to the one before it may only be placed after that one is already in the path.
function permuteUnique(nums) { const a = [...nums].sort((x, y) => x - y); // equal values next to each other const result = []; const path = []; const used = new Array(a.length).fill(false); const build = () => { if (path.length === a.length) { result.push([...path]); return; } for (let i = 0; i < a.length; i++) { if (used[i]) continue; if (i > 0 && a[i] === a[i - 1] && !used[i - 1]) continue; // equal values go in order used[i] = true; path.push(a[i]); build(); path.pop(); used[i] = false; } }; build(); return result;}Time O(n · n!) in the worst case (all distinct), but proportional to the number of unique permutations when there are duplicates. Space O(n).
a[i] === a[i − 1] check needs equal values side by side.