Permutations I and Permutations II

47.Permutations II

Backtracking

Hash Table

Recursion

Problem Statement:

Given an array nums o integers, return all possible permutations. The solution set must not contain duplicate permutations.

Example:

Input:

nums = [1,1,2]

→

Output:

[[1,1,2], [1,2,1], [2,1,1]]

Algorithm:

1. Use HashMap to count frequencies
2. Backtrack using frequency count
3. Decrement count while exploring
4. Restore count when backtracking

Complexity:

Time: O(n!) | Space: O(n)

Java Solution:

public ListInteger>> permute(int[] nums) {
    ListInteger>> result = new ArrayList<>();
    Map<Integer, Integer> countMap = new HashMap<>();
    List<Integer> tempList = new ArrayList<>();
    
    // Count frequency of each number
    for (int num : nums) {
        countMap.put(num, countMap.getOrDefault(num, 0) + 1);
    }
    
    permute(nums, result, countMap, tempList);
    return result;
}

private void permute(int[] nums, 
        ListInteger>> result, 
        Map<Integer, Integer> countMap, 
        List<Integer> tempList) {
    
    // Found valid permutation
    if (tempList.size() == nums.length) {
        result.add(new ArrayList<>(tempList));
        return;
    }
    
    // Try each number based on remaining count
    for (int num : countMap.keySet()) {
        int count = countMap.get(num);
        
        if (count > 0) {
            countMap.put(num, count - 1);  // Use number
            tempList.add(num);
            
            permute(nums, result, countMap, tempList);
            
            tempList.remove(tempList.size() - 1);  // Restore
            countMap.put(num, count);
        }
    }  
}

Python Solution:

def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    result = []
    count = Counter(nums)
    
    def backtrack(temp: List[int]):
        # Found valid permutation
        if len(temp) == len(nums):
            result.append(temp[:])
            return
        
        # Try remaining numbers
        for num in count:
            if count[num] > 0:
                count[num] -= 1
                temp.append(num)
                
                backtrack(temp)
                
                temp.pop()
                count[num] += 1
                
    backtrack([])
    return result

C++ Solution:

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