这是一个排列问题,但不能有重复数字,所以在进行递归回溯的时候,需要进行限制条件。也就是在单层搜索逻辑下的for循环侧进行限制。那我们先来看看回溯的模板
void backtracking(参数){ if(终止条件){ 存放结果; return; } for(选择:本层集合中元素(树中节点孩子的数量就是集合的大小)){ 处理节点 backtracking(路劲,选择列表);//递归 回溯,撤销处理结果 } }那么如何进行限制呢?这里需要用到一个标记数组,每次使用过这个数后对其进行标记,再使用下一个数的时候,只需要比较前一个数是否已经使用就可以了
最关键的是,需要对数组先进行排序
class Solution { //存放结果 List<List<Integer>> result = new ArrayList<>(); //暂存结果 List<Integer> path = new ArrayList<>(); public List<List<Integer>> permuteUnique(int[] nums) { boolean[] used = new boolean[nums.length]; Arrays.fill(used, false); Arrays.sort(nums); backTrack(nums, used); return result; } private void backTrack(int[] nums, boolean[] used) { if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { // used[i - 1] == true,说明同⼀树⽀nums[i - 1]使⽤过 // used[i - 1] == false,说明同⼀树层nums[i - 1]使⽤过 // 如果同⼀树层nums[i - 1]使⽤过则直接跳过 if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; } //如果同⼀树⽀nums[i]没使⽤过开始处理 if (used[i] == false) { used[i] = true;//标记同⼀树⽀nums[i]使⽤过,防止同一树枝重复使用 path.add(nums[i]); backTrack(nums, used); path.remove(path.size() - 1);//回溯,说明同⼀树层nums[i]使⽤过,防止下一树层重复 used[i] = false;//回溯 } } } }