3 different Java solution for this question with detailed explanation


  • 2
    Y
    public class Solution {
        /**
         * If we are allowed to sort the array, we could sort the array to let the same number cluster together. 
         * In this way, avoiding duplicates, which is to avoid the same number being the first number in the permutation, is simplified because we can judge is a number is the same as its previous one and if its previous one has been used. 
         * We keep a boolean array to store the numbers being used, whose values are false originally. 
         * Each time we use a number, we set its corresponding value in boolean array to be true. 
         * And we try further down in the recursion. 
         * Once the recursion returns, we backtrack by changing its corresponding boolean value to be false and remove it from the current result.
         * O(n!) time, O(n) space.
         */
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> ret = new ArrayList<>();
            if (nums == null || nums.length == 0) return ret;
            
            Arrays.sort(nums);
            boolean[] used = new boolean[nums.length];
            
            permuteHelper(nums, 0, ret, used, new ArrayList<Integer>());
            
            return ret;
        }
        
        private void permuteHelper(int[] nums, int len, List<List<Integer>> ret, boolean[] used, List<Integer> curr) {
            if (len == nums.length) {
                ret.add(new ArrayList<Integer>(curr));
                return;
            }
            
            for (int i = 0; i < nums.length; i++) {
                if (!used[i]) {
                    if (i > 0 && nums[i] == nums[i - 1] && used[i - 1]) {
                        continue;
                    }
                    used[i] = true;
                    curr.add(nums[i]);
                    permuteHelper(nums, len + 1, ret, used, curr);
                    curr.remove(curr.size() - 1);
                    used[i] = false;
                }
            }
        }
        
        
        
        /**
         * Based on the third method of permutations I, which is to swap 2 numbers in the array each time.
         * However, we want to avoid duplicates in this problem.
         * Avoiding duplicates in the permutations we got is actually avoiding let the same number to be the first number of the permutations. And this is also true in the subproblems we met. 
         * So we simply keep a hashset at each level of the recursion tree to store the numbers we have used as the first number of the permutations generated from this level
         * Once we find a number already existed in the hashset, we would skip this number.
         * Other ideas is the same as Permutations I. Swap 2 numbers each time, recurse, and swap back. A typical backtracking problem. 
         * O(n!) time. O(n ^ 2) space. The recursion would be n-level in depth. 
         */
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> ret = new ArrayList<>();
            if (nums == null || nums.length == 0) return ret;
            
            permuteHelper(nums, 0, ret);
            
            return ret;
        }
        
        private void permuteHelper(int[] nums, int pos, List<List<Integer>> ret) {
            if (pos == nums.length) {
                List<Integer> curr = new ArrayList<>();
                for (int num : nums) {
                    curr.add(num);
                }
                ret.add(curr);
                return;
            }
            
            Set<Integer> used = new HashSet<>();
            for (int i = pos; i < nums.length; i++) {
                if (used.add(nums[i])) {
                    swap(nums, pos, i);
                    permuteHelper(nums, pos + 1, ret);
                    swap(nums, pos, i); //Backtracking
                } 
            }
        }
        
        private void swap(int[] nums, int i, int j) {
            if (i == j) return;
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        
        
        /**
         * BackTracking. 
         * If the nums array cannot be changed (i.e. cannot sort the array), than we may need to keep some thing to record which number have been used. 
         * In this question, we keep a hashmap with the numbers in the nums as the key and the number of their appearance as value
         * So each time we used a number, we subtract its appearance by 1 and searching down by recursion. So we only use the number with appearance greater than 0. 
         * Once we reached the length of the nums, we add current result into the ret list. 
         * And by the time the recursion returns, we backtrack by adding back 1 to the appearance and remove the last number of current result. 
         * O(n! *) time, O(n) space with consider the recursion stack. The recursion stack would consume O(n) space since the recursion would be n-level in depth where n is the length of nums. 
         */
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> ret = new ArrayList<>();
            if (nums == null || nums.length == 0) return ret;
            Map<Integer, Integer> used = new HashMap<Integer, Integer>();//<number, appearance>
            for (int num : nums) {
                if (used.containsKey(num)) {
                    used.put(num, used.get(num) + 1);
                } else {
                    used.put(num, 1);
                }
            }
            permuteHelper(nums, 0, ret, new ArrayList<Integer>(), used);
            
            return ret;
        }
        
        private void permuteHelper(int[] nums, int start, List<List<Integer>> ret, List<Integer> curr, Map<Integer, Integer> used) {
            if (start == nums.length) {
                ret.add(new ArrayList<Integer>(curr));
                return;
            }
            
            Set<Integer> keys = used.keySet();
            for (Integer key : keys) { //iterate through the hashmap to generate permutations
                if (used.get(key) > 0) {
                    used.put(key, used.get(key) - 1);
                    curr.add(key);
                    permuteHelper(nums, start + 1, ret, curr, used);
                    curr.remove(curr.size() - 1);
                    used.put(key, used.get(key) + 1);
                }
            }
        }
    }
    

  • 0
    K

    @YaokaiYang I like the second solution. Very good. I liked it a lot.


  • 0
    X

    @YaokaiYang one question , why backtrack is O(n! * n) time


  • 0
    Y

    @xiaowu4 I'm sorry, I think it should be O(n!) time.


  • 0
    X

    @YaokaiYang I think it's O(n!), and your solution it's very good. By the way, are you Chinese?


  • 0
    Y

    @xiaowu4 Thank you. I am Chinese.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.