穷举vs暴搜vs深搜vs回溯vs剪枝专题一＞全排列II

题目：

 

---

解析： 

这题设计递归函数，主要把看如何剪枝 

 

---

代码： 

class Solution {private List<List<Integer>> ret;private List<Integer> path;private boolean[] check;public List<List<Integer>> permuteUnique(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[nums.length];Arrays.sort(nums);//dfs(nums,0);return ret;}//pos是决策树层数private void dfs(int[] nums,int pos){if(pos == nums.length){ret.add(new ArrayList<>(path));return;}for(int i = 0; i < nums.length; i++){ //不合法分支剪枝if(check[i] == true || i != 0 && nums[i] == nums[i-1] && check[i-1] == false)continue;if(check[i] == false){path.add(nums[i]);check[i] = true;dfs(nums,pos+1);//恢复现场path.remove(path.size()-1);check[i] = false;}}}
}