47. Permutations II

Medium

Problem Description

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

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]]
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def permuteUnique(nums: List[int]) -> List[List[int]]:
    def backtrack(counter, path):
        if len(path) == len(nums):
            result.append(path[:])
            return
        
        for num in counter:
            if counter[num] > 0:
                counter[num] -= 1
                path.append(num)
                backtrack(counter, path)
                path.pop()
                counter[num] += 1
    
    result = []
    counter = Counter(nums)
    backtrack(counter, [])
    return result

Java Solution


class Solution {
    private List> result = new ArrayList<>();
    
    public List> permuteUnique(int[] nums) {
        Map counter = new HashMap<>();
        for (int num : nums) {
            counter.put(num, counter.getOrDefault(num, 0) + 1);
        }
        
        backtrack(counter, new ArrayList<>(), nums.length);
        return result;
    }
    
    private void backtrack(Map counter, List path, int n) {
        if (path.size() == n) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (Map.Entry entry : counter.entrySet()) {
            int num = entry.getKey();
            int count = entry.getValue();
            
            if (count > 0) {
                counter.put(num, count - 1);
                path.add(num);
                backtrack(counter, path, n);
                path.remove(path.size() - 1);
                counter.put(num, count);
            }
        }
    }
}

C++ Solution


class Solution {
public:
    vector> permuteUnique(vector& nums) {
        vector> result;
        unordered_map counter;
        for (int num : nums) {
            counter[num]++;
        }
        
        vector path;
        backtrack(counter, path, nums.size(), result);
        return result;
    }
    
private:
    void backtrack(unordered_map& counter, vector& path, 
                  int n, vector>& result) {
        if (path.size() == n) {
            result.push_back(path);
            return;
        }
        
        for (auto& [num, count] : counter) {
            if (count > 0) {
                counter[num]--;
                path.push_back(num);
                backtrack(counter, path, n, result);
                path.pop_back();
                counter[num]++;
            }
        }
    }
};

JavaScript Solution


/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    const result = [];
    const counter = new Map();
    
    // Count frequency of each number
    for (const num of nums) {
        counter.set(num, (counter.get(num) || 0) + 1);
    }
    
    const backtrack = (path) => {
        if (path.length === nums.length) {
            result.push([...path]);
            return;
        }
        
        for (const [num, count] of counter) {
            if (count > 0) {
                counter.set(num, count - 1);
                path.push(num);
                backtrack(path);
                path.pop();
                counter.set(num, count);
            }
        }
    };
    
    backtrack([]);
    return result;
};

C# Solution


public class Solution {
    private IList> result = new List>();
    
    public IList> PermuteUnique(int[] nums) {
        Dictionary counter = new Dictionary();
        foreach (int num in nums) {
            if (!counter.ContainsKey(num)) {
                counter[num] = 0;
            }
            counter[num]++;
        }
        
        Backtrack(counter, new List(), nums.Length);
        return result;
    }
    
    private void Backtrack(Dictionary counter, List path, int n) {
        if (path.Count == n) {
            result.Add(new List(path));
            return;
        }
        
        foreach (var pair in counter.ToList()) {
            int num = pair.Key;
            int count = pair.Value;
            
            if (count > 0) {
                counter[num]--;
                path.Add(num);
                Backtrack(counter, path, n);
                path.RemoveAt(path.Count - 1);
                counter[num]++;
            }
        }
    }
}

Complexity Analysis

Solution Explanation

This solution uses backtracking with a frequency counter to handle duplicates. Here's how it works:

Key points: