文章目录
先分析一下这道题目的区别，
首先46题题中要求是不含重复元素，所以我们在进行回溯的时候不需要对数据进行去重、
其次47题题中说明了含有重复元素，所以我们在进行回溯过程中需要对数据进行去重。那么我们怎么去重呢？
上面两道题我们使用传统的回溯写法很容易就可以写出来，但是对于47题难点是对数据进行去重，这里我们需要解释一下卡子哥自创的树枝去重和树层去重
我们用树化的思维去寻找符合条件的值，存在多个同一个数的时候，在同一个树枝上可以重复，对于同一层来说，如果再取这个数据就会出现重复，一般用一个used数据来表示，不太理解的话可以先记住，多做几道题就理解了。（我大概遇到五六道题就慢慢理解了）。
树层去重：
if(i>0 && num[i] == nums[i-1] && used[i-1] == false)
树枝去重：
if(i>0 && num[i] == nums[i-1] && used[i-1] == true)
这里我给出两道题的示例代码，仔细品一品吧。
全排序I
class Solution { List<List<Integer>> list = new ArrayList<>(); LinkedList<Integer> list1 = new LinkedList<>(); boolean[] used; public List<List<Integer>> permute(int[] nums) { if(nums.length == 0){ list.add(new ArrayList<>(list1)); return list; } used = new boolean[nums.length]; HiSir(nums); return list; } public void HiSir(int[] nums){ if(list1.size() == nums.length){ list.add(new ArrayList<>(list1)); return; } for(int i = 0;i<nums.length;i++){ if(used[i]){ continue; } used[i] = true; list1.add(nums[i]); HiSir(nums); used[i] = false; list1.removeLast(); } } }
全排序II
class Solution { List<List<Integer>> list = new ArrayList<>(); LinkedList<Integer> list1 = new LinkedList<>(); boolean[] used; public List<List<Integer>> permuteUnique(int[] nums) { if(nums.length == 0){ list.add(new ArrayList<>(list1)); return list; } used = new boolean[nums.length]; Arrays.fill(used,false); Arrays.sort(nums); HiSir(nums); return list; } public void HiSir(int[] nums){ if(list1.size() == nums.length){ list.add(new ArrayList<>(list1)); return; } for(int i =0;i<nums.length;i++){ if(i >0 && nums[i] == nums[i-1] && used[i-1] == false){ continue; } if(used[i] == false){ used[i] = true; list1.add(nums[i]); HiSir(nums); list1.removeLast(); used[i] = false; } } } }
