My java backtrack solution using map


  • 0
    L
    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            Arrays.sort(nums);
            backtrack(result,new ArrayList<Integer>(),nums,0);
            return result;
        }
    
        private void backtrack(List<List<Integer>> result,List<Integer> cur,int[] nums,int start){
            if(start == nums.length){
                result.add(new ArrayList<Integer>(cur));
                return;
            }
    
            Map<Integer,Boolean> map = new HashMap<Integer,Boolean>();
            for(int k:nums){
                map.put(k,false);
            }
    
    
            // 所有孩子应是在他之后的所有元素和这个start交换后看
            int i = start;
            while(i<nums.length){
                if(!map.get(nums[i])) {
                    map.put(nums[i], true);
                    //把第i个换到开头
                    swap(nums, start, i);
    
                    cur.add(nums[start]);
                    backtrack(result, cur, nums, start + 1);
                    cur.remove(cur.size() - 1);
    
                    //把第i个换回来
                    swap(nums, start, i);
                }
                    ++i;
            }
        }
    
        private void swap(int[] nums,int l,int r){
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
        }
    }

Log in to reply
 

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