LeetCode中涉及到回溯的题目有通用的解题套路：

 46. permutations

这一类回溯题目中的基础中的基础，无重复数字枚举：

1 /* Given a collection of distinct numbers, return all possible permutations. 2  3 For example, 4 [1,2,3] have the following permutations: 5 [ 6   [1,2,3], 7   [1,3,2], 8   [2,1,3], 9   [2,3,1],10   [3,1,2],11   [3,2,1]12 ] */13 14 public class Solution {15     public List
     
      
       > permute(int[] nums) {16         List
       
        
         > res = new ArrayList<>();17         backtrack(res, new ArrayList<>(), nums);18         return res;19     }20     public void backtrack(List
         
          
           > list, List
           
             tmp, int[] nums){21 if(tmp.size() == nums.length)22 list.add(new ArrayList<>(tmp)); //要重新new一个list进去23 else{24 for(int i = 0; i < nums.length; i++){25 if(tmp.contains(nums[i])) continue;26 tmp.add(nums[i]);27 backtrack(list, tmp, nums);28 tmp.remove(tmp.size() - 1); //回溯的重要一步，恢复环境29 30 }31 }32 }33 }
           
          
         
        
       
      
     

47. permutations II 

稍微增加了点难度，有重复的数字，采取的技巧其实是相当于对重复的数字人为规定一个顺序

1 /* Given a collection of numbers that might contain duplicates, return all possible unique permutations. 2  3 For example, 4 [1,1,2] have the following unique permutations: 5 [ 6   [1,1,2], 7   [1,2,1], 8   [2,1,1] 9 ] */10 11 public class Solution {12     public List
     
      
       > permuteUnique(int[] nums) {13         List
       
        
         > res = new ArrayList<>();14         if(nums == null || nums.length == 0) return res;15         Arrays.sort(nums); //排序不要忘16         backtrack(res, new ArrayList<>(), nums, new boolean[nums.length]);17         return res;18     }19     public void backtrack(List
         
          
           > list, List
           
             tmp, int[] nums, boolean[] used){20 if(tmp.size() == nums.length)21 list.add(new ArrayList<>(tmp));22 else{23 for(int i = 0; i < nums.length; i++){24 if(used[i] || (i > 0 && nums[i-1] == nums[i] && !used[i-1])) continue;25 used[i] = true;26 tmp.add(nums[i]);27 backtrack(list, tmp, nums, used);28 used[i] = false;29 tmp.remove(tmp.size() - 1);30 }31 }32 }33 }