代码随想录day22：回溯part4

ops/2024/10/9 9:03:33/

491.递增子序列

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backTracking(nums, 0);return result;}private void backTracking(int[] nums, int startIndex){if(path.size() >= 2)result.add(new ArrayList<>(path));            HashSet<Integer> hs = new HashSet<>();for(int i = startIndex; i < nums.length; i++){if(!path.isEmpty() && path.get(path.size() -1 ) > nums[i] || hs.contains(nums[i]))continue;hs.add(nums[i]);path.add(nums[i]);backTracking(nums, i + 1);path.remove(path.size() - 1);}}
}

对于已经习惯写回溯的同学，看到递归函数上面的uset.insert(nums[i]);，下面却没有对应的pop之类的操作，应该很不习惯吧

这也是需要注意的点，unordered_set<int> uset; 是记录本层元素是否重复使用，新的一层uset都会重新定义（清空），所以要知道uset只负责本层！

46.全排列

排列问题是用used数组树枝去重；组合问题（无重复元素）的用startIndex去重，有重复元素的要做数层去重（used数组或者hashset）

class Solution {List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果boolean[] used;public List<List<Integer>> permute(int[] nums) {if (nums.length == 0){return result;}used = new boolean[nums.length];permuteHelper(nums);return result;}private void permuteHelper(int[] nums){if (path.size() == nums.length){result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++){if (used[i]){continue;}used[i] = true;path.add(nums[i]);permuteHelper(nums);path.removeLast();used[i] = false;}}
}

47.全排列 II

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;//回溯}}}
}