LeetCode T491 递增子序列
题目链接:491. 递增子序列 - 力扣（LeetCode）
题目思路:
首先这里的测试用例很容易误导我们,这道题不能使用上次子集的思路对数组先排序,使用一个used数组来解决问题.
我们用[4,7,6,7]举例这道题的递增序列不存在[4,6,7,7]这个子序列,而如果我们对数组先进行排序,就会得到错误答案.
这题的实质是让我们在数组中递增的取出元素,实际上是我们取出的元素是有序的,这里我们可以定义一个set来解决问题,实际上我们要做的仍然是树层去重,这里只要对每一层的元素进行一次去重即可
1.函数定义
其他的都定义为全局变量了,只需这两个参数即可
public void backtracking(int[] nums,int startIndex)
2.终止条件
这题跟之前一样,不需要终止条件,因为我们收集的是树的所有节点,而不是叶子结点,但是题目要求我们的path至少要大于等于2,所以我们就以这个为条件来收集结果.
if(path.size()>=2) { result.add(new ArrayList(path)); }
3.一次搜索逻辑(for循环)
注:为什么set不需要回溯?
因为set是每一层都会重置的,无需回溯,每一层回溯会自动置空
Set<Integer> set = new HashSet<>();//每一层用来记录,去重 for(int i = startIndex;i<nums.length;i++) { if( !path.isEmpty() && path.get(path.size()-1) > nums[i] || set.contains(nums[i])) { continue; } set.add(nums[i]); path.add(nums[i]); backtracking(nums,i+1); path.remove(path.size()-1); }
题目代码:
class Solution { List<Integer> path = new ArrayList<>(); List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> findSubsequences(int[] nums) { backtracking(nums,0); return result; } public void backtracking(int[] nums,int startIndex) { if(path.size()>=2) { result.add(new ArrayList(path)); } Set<Integer> set = new HashSet<>(); for(int i = startIndex;i<nums.length;i++) { if( !path.isEmpty() && path.get(path.size()-1) > nums[i] || set.contains(nums[i])) { continue; } set.add(nums[i]); path.add(nums[i]); backtracking(nums,i+1); path.remove(path.size()-1); } } }
LeetCode T46 全排列
题目思路:
首先这题我们可以先画出树状图,这题的重点就是used数组的使用
因为排列是有序的,所以[1,2]和[2,1]是两个完全不同的排列,这里可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex,但是需要使用used数组,因为一个排列中nums数组中的每个元素都只能出现一次,这里我们就需要标记已经出现的元素,如果它还想出现,就可以直接continues这次循环即可,下面我们进行回溯三部曲
1.回溯函数参数
这里不需要根据startIndex来判断取值区间,也是和子集不同的地方,这里我们直接传入nums数组即可
public void backtracking(int[] nums)
2.确定终止条件
这里是在叶子结点取值而不是取每个节点的值,所以需要终止条件,因为我们需要获得的是数组的排列,所以当path收集的元素长度到达数组的长度,即是一次有效的排列
if(path.size() == nums.length) { result.add(new ArrayList(path)); return; }
3.一次搜索逻辑
这里我们首先不能再一次排列中重复出现某元素,所以在添加元素之前先判断该元素是否出现过,出现过那么该次全排列无效,则跳出本轮循环,下面就是经典的递归和回溯过程
for(int i = 0;i<nums.length;i++) { if(used[i]) { continue; } path.add(nums[i]); used[i] = true; backtracking(nums); path.remove(path.size()-1); used[i] = false; }
题目代码:
class Solution { List<Integer> path = new ArrayList<>(); List<List<Integer>> result = new ArrayList<>(); boolean[] used; public List<List<Integer>> permute(int[] nums) { used = new boolean[nums.length]; backtracking(nums); return result; } public void backtracking(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; } path.add(nums[i]); used[i] = true; backtracking(nums); path.remove(path.size()-1); used[i] = false; } } }
LeetCode T47 全排列II
题目链接:47. 全排列 II - 力扣（LeetCode）
题目思路:
这题的思路和上一题类似,由于本题可能存在重复元素,所以比上一题多了一个去重的逻辑,这题的去重逻辑和之前组合的逻辑是一样的,我们只需要先将数组排序,让相同的元素排在一起,使用一个used数组来标记已经使用过的元素,这里我们还是先画出树状图来帮助理解
我们发现相邻元素如果是相等的,那么相同元素中的第二个元素开始的路径就重复了,也就是我们说的树层去重,下面我摆出树层去重的逻辑
if(i>0 && nums[i] == nums[i-1] && !used[i-1])
其余代码和上面一样,我们依然按照回溯三部曲来操作
1.函数参数
由于其他元素都定义为全局变量了,所以直接使用一个nums即可,本题不需要startIndex来帮助我们规定选择元素的区间
public void backtracking(int[] nums)
2.终止条件
这题终止条件仍然是path收集的长度到达nums的长度即可
if(path.size() == nums.length) { result.add(new ArrayList(path)); }
3.一次搜索逻辑
这里就涉及我们的去重逻辑了,下面由于没有startIndex约束,所以我们对选取的元素增加一个条件,就是选取的元素必须没有被使用过
for(int i = 0;i<nums.length;i++) { if(i>0 && nums[i] == nums[i-1] && !used[i-1]) { continue; } if (!used[i]) { used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用 path.add(nums[i]); backtracking(nums); path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复 used[i] = false;//回溯 } }
题目代码:
class Solution { List<Integer> path = new ArrayList<>(); List<List<Integer>> result = new ArrayList<>(); boolean used[]; public List<List<Integer>> permuteUnique(int[] nums) { used = new boolean[nums.length]; Arrays.sort(nums); backtracking(nums); return result; } public void backtracking(int[] nums) { if(path.size() == nums.length) { result.add(new ArrayList(path)); } for(int i = 0;i<nums.length;i++) { if(i>0 && nums[i] == nums[i-1] && !used[i-1]) { continue; } if (!used[i]) { used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用 path.add(nums[i]); backtracking(nums); path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复 used[i] = false;//回溯 } } } }
