Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/47.html

47 Permutations II

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

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

@tag-backtracking

Algorithm

Due to the possibility of repeated numbers in the input array, if you follow the previous algorithm, there will be repeated permutations. We need to avoid repetition. In the recursive function, we must determine whether the previous number is equal to the current number. If it is equal, and its The value in the corresponding visited is 1, the current number can be used (the reason for this will be explained below), otherwise it needs to be skipped, so that no duplication will occur.

Note

1 . use the idea of insertion sort: Loop through the array, in each iteration, a new number is added to different locations of results of previous iteration.

2 . to skip duplicates, two ways: 1. act on permutation_I result, use a set to filter duplicated results: bulky and extra o(N) operations and o(N) space 2. truncate during iteration or recursion, but: need sort nums[] array first, extra o(NlogN) operations

Code

  • import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Set;
    
    public class Permutations_II {
    
    	public static void main(String[] args) {
    		Permutations_II out = new Permutations_II();
    		Solution_recursion s = out.new Solution_recursion();
    
    		List<ArrayList<Integer>> result = s.permuteUnique(new int[]{1,1,2});
    		System.out.println(result.toString()); // output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
    	}
    
    
        // time: O(N)
        // space: O(N)
        public class Solution_recursion {
    
            ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    
            public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
    
                if (num == null && num.length == 0)
                    return res;
    
                Arrays.sort(num);
    
                dfs(num, new boolean[num.length], new ArrayList<Integer>());
    
                return res;
            }
    
            // @para: used by index
            private void dfs(int[] num, boolean[] used, ArrayList<Integer> onePerm) {
    
                if (onePerm.size() == num.length) {
                    res.add(new ArrayList<Integer>(onePerm));
                    return;
                }
    
                for (int i = 0; i < num.length; i++) {
    
                    // @note: !used[i-1], here “-1” to skip if prev used
                    if (i > 0 && !used[i - 1] && num[i] == num[i - 1])
                        continue;
    
                    if (!used[i]) {
                        used[i] = true;
                        onePerm.add(num[i]);
    
                        dfs(num, used, onePerm);
    
                        onePerm.remove(onePerm.size() - 1);
                        used[i] = false;
                    }
                }
            }
        }
    
    	public class Solution_hashset_for_unique {
    	    public List<List<Integer>> permuteUnique(int[] nums) {
    
    	        List<List<Integer>> list = new ArrayList<>();
    
    	        if (nums == null || nums.length == 0) {
    	            return list;
    	        }
    
    	        list.add(new ArrayList<Integer>()); // add empty single list, to make below loop going
    
    	        for (int i = 0; i < nums.length; i++) {
    
    	            List<List<Integer>> tmpList = new ArrayList<>();
    	            int insertNum = nums[i];
    
    	            // get each permutations. eg, [1,2], [2,1]
    	            for (List<Integer> singlePerm: list) {
    
    	                /*
    	                    @note: I made big mistake below, in for(): index<list.size(), but inside add one more to list, so infinite loop...
    	                */
    
    	                // eg. [1,2] and insert 3, there are 3 insert position
    	                // for (int index = 0; index <= singlePerm.size(); index++) { // @note: the usage of arraylist add() api: add(atIndex, value)
    	                int singleListSize = singlePerm.size();
    	                for (int index = 0; index <= singleListSize; index++) { // @note: the usage of arraylist add() api: add(atIndex, value)
    	                    singlePerm.add(index, insertNum);
    	                    tmpList.add(new ArrayList<Integer>(singlePerm));
    
    	                    // @note: don't forget roll back
    	                    singlePerm.remove(index);
    	                }
    	            }
    
    	            // udpate list
    	            list = tmpList;
    	        }
    
    	        /*
    	         * option 1: sort, and skip duplicated digits => o(NlogN)
    	         * option 2: keep all, then remove duplication, each pair comparison => o(N^2)
    	         */
    
    	        // hacky way, work based on permutation_I result
    	        Set<List<Integer>> hs = new HashSet<>();
    	        hs.addAll(list);
    	        list.clear();
    	        list.addAll(hs);
    
    	        return list;
    	    }
    
    	}
    }
    
  • // OJ: https://leetcode.com/problems/permutations-ii
    // Time: O(N! * N)
    // Space: O(N^2)
    // Ref: https://discuss.leetcode.com/topic/8831/a-simple-c-solution-in-only-20-lines
    class Solution {
    private:
      vector<vector<int>> ans;
      void permute(vector<int> nums, int start) {
        if (start == nums.size() - 1) {
          ans.push_back(nums);
          return;
        }
        for (int i = start; i < nums.size(); ++i) {
          if (i != start && nums[i] == nums[start]) continue;
          swap(nums[i], nums[start]);
          permute(nums, start + 1);
        }
      }
    public:
      vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        permute(nums, 0);
        return ans;
      }
    };
    
  • class Solution: # iterative
        def permuteUnique(self, nums: List[int]) -> List[List[int]]:
            nums.sort() # sort the input to handle duplicates
            res = [[]]
            for num in nums:
                new_res = []
                for perm in res:
                    for i in range(len(perm) + 1):
                        if i > 0 and perm[i - 1] == num:
                            break # skip duplicate
                        new_perm = perm[:i] + [num] + perm[i:] # or perm.insert(index, num), like in lc-46
                        new_res.append(new_perm)
                res = new_res
            return res
    
    ############
    
    class Solution: # dfs
        def permuteUnique(self, nums: List[int]) -> List[List[int]]:
            res = []
            visited = set([])
            nums.sort() # added from lc-47
    
            def dfs(nums, path, res, visited):
                if len(path) == len(nums):
                    res.append(path + [])
                    return
        
                for i in range(0, len(nums)):
                    if i > 0 and nums[i - 1] == nums[i] and i - 1 not in visited: # added from lc-47
                        continue
                    if i not in visited:
                        visited.add(i)
                        path.append(nums[i])
                        dfs(nums, path, res, visited)
                        path.pop()
                        visited.discard(i) # or remove(i)
    
            dfs(nums, [], res, visited)
            return res
    
    

All Problems

All Solutions