Java DFS+backtracking solution 7 ms with explanation


  • 0
    Z

    This is standart top to down approach solution. To understand imagine an array containing two elements only. This case, we would add the array itself to the result, then swap the elements and add again to the result. That's it. If array contains three elements then we would do the operations mentioned above for the last two elements, then for each possible position of the current element we would append the current state of the array to the result. The same way, at every top level, we find permutations of the suffix array and for each possible position of the current element, add the current state of the array to the result.
    A couple of additional statements needed to eliminate duplicates from the resultant permutations. They are implemented at line #23, and from line #39 to line #41.

    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if(nums.length == 0){
                return res;
            }
            if(nums.length == 1){
                List<Integer> list  = new ArrayList<>();
                list.add(nums[0]);
                res.add(list);
                return res;
            }
            dfs(res, nums, 0);
            return res;
        }
        
        public void dfs(List<List<Integer>> res, int nums[], int start){
            if(nums.length-start == 2){
                List<Integer> pair = new ArrayList<>();
                pair.add(nums[start]);
                pair.add(nums[start+1]);
                res.add(pair);
                if(nums[start] != nums[start+1]){ //line #23
                    List<Integer> revPair = new ArrayList<>();
                    revPair.add(nums[start+1]);
                    revPair.add(nums[start]);
                    res.add(revPair);
                }                            
                return;
            }
            dfs(res, nums, start+1);
            int size = res.size();
            for(int j = 0;j<size;j++){
                List<Integer> list = res.get(0);
                res.remove(0);
                list.add(0, nums[start]);
                res.add(new ArrayList<>(list));
                for(int jj = 1;jj<list.size();jj++){
                    if(list.get(jj) == nums[start]){ // line #39
                        break;    
                    }                                // line #41
                    Collections.swap(list, jj-1,jj);
                    res.add(new ArrayList<>(list));
                }
            }
        }
    }
    

Log in to reply
 

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