One simple method that solves many similar problems


  • 0
    A

    First, you need to recall that such problems can be solved with backtracking, i.e. every time you fall into the next level of your recursion where you need to follow the same procedure but with the result of the previous step in your mind.

    In this particular problem, remember the number that you have chosen in the previous step (in the upper level of the recursion). This can be done using regular boolean array where each index shows if the corresponding index in the numbers array is used or not. So if the index is set to true, then the number at that index has already been used and added to the running list. So simply select the next unset number in your numbers array. The problem here though is that the numbers may repeat, i.e. having repeated elements leads to duplicate lists in your answer. In order to take care of it, recall the solutions from https://leetcode.com/problems/combination-sum-ii/description/ and https://leetcode.com/problems/permutations/. The combination of their solutions lead to a simple but elegant solution.

    I attach the full code below with some description.

    class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            if (nums == null) {
                return new ArrayList<>();
            }
            
            Arrays.sort(nums); // sort to take care of duplicates
            List<List<Integer>> combs = new ArrayList<>(); // final answer
            permuteHelper(combs, new ArrayList<>(), new boolean[nums.length], nums);
            
            return combs;
        }
        
        private void permuteHelper(List<List<Integer>> combs, List<Integer> runningList,
                                  boolean[] used, int[] nums) {
            if (runningList.size() == nums.length) {  // if we have all the numbers in the list
                combs.add(new ArrayList<>(runningList));
                return;
            }
            
            boolean firstSeen = false; // if we have seen the first unused element
            int lastSeen = nums[0]; // what is the last seen element in the array
            
            for (int i = 0; i < nums.length; i++) {
                if (firstSeen && nums[i] == lastSeen) {
                    continue;
                }
                if (used[i]) {
                    continue;
                }
                
                firstSeen = true; // this is the first unused element
                lastSeen = nums[i]; // lastSeen is the current unused element
                used[i] = true;
                runningList.add(nums[i]);
                permuteHelper(combs, runningList, used, nums);
                runningList.remove(runningList.size()-1);
                used[i] = false;
            }
        }
    }
    

    Let me know if you can improve or make the solution more efficient, or if you have any questions.


Log in to reply
 

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