47.Permutations_II(Medium).md

47. Permutations II (Medium)

Date and Time: May 1, 2025

Link: https://leetcode.com/problems/permutations-ii

Walk-through:

Similar to 46.Permutations, we can run backtrack with subset[] and a hashmap rest_map{}, which we can choose the next integer from and append it to subset[] for the next backtrack() call.

Python:

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # Q: return all unique permutations
        # S: Similar to 46. Permutations, we can use a hashmap to store each integer's count, and we just call backtrack on (subset, rest_map)
        # For each backtrack, we choose integer from rest_map{}, check if the count of this integer > 0, we append this one to subset[] and decrement this int's count on rest_map. After this backtrack is done, we increment the count of this integer back.
        # TC: O(n * n!), n=len(nums), SC: O(n * n!)

        # 1. Build hashmap
        hashmap = collections.defaultdict(int)
        for i in nums:
            hashmap[i] += 1
        # 2. Run backtrack() to find ans[]
        ans = []
        def backtr(subset, rest_map):
            if len(subset) == len(nums):
                ans.append(subset.copy())
            # Check the rest integers from rest_map
            for i in rest_map:
                if rest_map[i] > 0:
                    rest_map[i] -= 1
                    backtr(subset + [i], rest_map)
                    rest_map[i] += 1
        backtr([], hashmap)
        return ans

Time Complexity: $O(n * n!)$
Space Complexity: $O(n * n!)$

Java

class Solution {
    /* 
    Similar to 46.permutations, we need to call backtr on (subset, rest_map), which each time we add integer i to subset and decrement count of i, and pass these to next backtr()
    TC: O(n * n!), SC: O(n * n!)
    */
    int[] nums;
    List<List<Integer>> ans = new ArrayList<>();
    Map<Integer, Integer> hashmap = new HashMap<>();    // {integer: count}

    private void backtr(List<Integer> subset, Map<Integer, Integer> rest_map) {
        if (subset.size() == nums.length) {
            ans.add(new ArrayList<>(subset));
        }
        // Check other integer i and add into subset, update rest_map
        for (int i: rest_map.keySet()) {
            // Add into subset if count of integer i > 0
            if (rest_map.get(i) > 0) {
                subset.add(i);
                rest_map.put(i, rest_map.get(i) - 1);
                backtr(subset, rest_map);
                subset.remove(subset.size() - 1);
                rest_map.put(i, rest_map.get(i) + 1);
            }
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        this.nums = nums;
        // 1. Fill in hashmap
        for (int i: nums) {
            hashmap.put(i, hashmap.getOrDefault(i, 0) + 1);
        }
        // 2. Call backtr()
        backtr(new ArrayList<>(), hashmap);
        return ans;
    }
}