1、leetcode491 递增子序列
-
回溯三部曲
-
递归参数
-
本题求子序列,很明显一个元素不能重复使用,所以需要startIndex,调整下一层递归的起始位置。
-
List<Integer> path = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); public void backTracking(int[] nums, int startIndex) { }
-
-
递归终止条件
-
题目要求递增子序列大小至少为2 且 startIndex每次都会加1,并不会无限递归。
if(path.size() > 1) { res.add(new ArrayList<>(path)); // 注意这里不要加return,因为要取树上的所有节点 }
-
-
单层搜索逻辑
- 同一父节点下的同层上使用过的元素就不能再使用了
-
-
代码
class Solution { private List<Integer> path = new ArrayList<>(); private List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> findSubsequences(int[] nums) { backtracking(nums,0); return res; } private void backtracking (int[] nums, int start) { if (path.size() > 1) { res.add(new ArrayList<>(path)); // 注意这里不要加return,要取树上的节点 } int[] used = new int[201]; // 这里使用数组来进行去重操作,题目说数值范围[-100, 100] for (int i = start; i < nums.length; i++) { if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) || (used[nums[i] + 100] == 1)) continue; used[nums[i] + 100] = 1; // 记录这个元素在本层用过了,本层后面不能再用了 path.add(nums[i]); backtracking(nums, i + 1); path.remove(path.size() - 1); } } }
注意:
数组,set,map都可以做哈希表,而且数组干的活,map和set都能干,但如果数值范围小的话能用数组尽量用数组
2、leetcode46 全排列
-
回溯三部曲
-
递归参数
-
首先排列是有序的。
-
可以看出元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理排列问题就不用使用startIndex了。
-
但排列问题需要一个used数组,标记已经选择的元素
- used数组,其实就是记录此时path里都有哪些元素使用了,一个排列里一个元素只能使用一次
-
List<Integer> path = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); public void backTracking(int[] nums, boolean[] used) { }
-
-
递归终止条件
- 当收集元素的数组path的大小达到和nums数组一样大的时候,说明找到了一个全排列,也表示到达了叶子节点。
-
单层搜索逻辑
for(int i=0; i<nums.length; i++) { if(used[i] == true) { // path里已经收录的元素,直接跳过 continue; } used[i] = true; //处理 path.add(nums[i]); //处理 backTracking(nums, used); //递归 used[i] = false; //回溯 path.remove(path.size()-1); //回溯 }
-
-
代码
class Solution { List<Integer> path = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { boolean[] used = new boolean[nums.length]; backTracking(nums, used); return res; } public void backTracking(int[] nums, boolean[] used) { if(path.size() == nums.length) { // 此时说明找到了一组 res.add(new ArrayList<>(path)); return; } for(int i=0; i<nums.length; i++) { if(used[i] == true) { // path里已经收录的元素,直接跳过 continue; } used[i] = true; //处理 path.add(nums[i]); //处理 backTracking(nums, used); //递归 used[i] = false; //回溯 path.remove(path.size()-1); //回溯 } } }
3、leetcode47 全排列Ⅱ
-
代码
class Solution { List<Integer> path = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> permuteUnique(int[] nums) { Arrays.sort(nums);// 排序 boolean[] used = new boolean[nums.length]; backTracking(nums, used); return res; } public void backTracking(int[] nums, boolean[] used) { if(path.size() == nums.length) { res.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>=1 && nums[i] == nums[i-1] && used[i-1] == true) { continue; } if(used[i] == false) { used[i] = true; path.add(nums[i]); backTracking(nums, used); used[i] = false; path.remove(path.size()-1); } } } }
-
对于排列问题,树层上去重和树枝上去重,都是可以的,但是树层上去重效率更高!