回溯---递增子序列 Posted on 2021-07-27 00:00:00 2021-07-27 00:00:00 by Author 摘要 给定一个整型数组, 你能找到所有该数组的递增子序列吗？？？？ # 递增子序列 1. 题目描述 - 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是 2 。 - **提示：** - 给定数组的长度不会超过15。 - 数组中的整数范围是 [-100,100]。 - 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。 2. 示例描述 - 示例一 - 输入：[4, 6, 7, 7] - 输出：[[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]] - 示例二 - 输入：[1,2,3] - 输出：[[1,2],[1,3],[2,3],[1,2,3]] 3. 解题思路 - 在拿到本题的时候，我发现这道题和之前回溯加递归的题一模一样，只要掌握掌握了递归与回溯算法，解决这道题就分分钟的事，但是写着写着发现自己还是太年轻了，这道题与之前的题还有点不太一样。不一样的地方在与递归寻找子序列过程中会出现重合的子集，在去重的这方面我卡住了，不知道怎么下手去重。 - 想了好久还是么想出来，于是就参考代码随想录Carl哥的题解，发现他的讲解思路真的太清楚了，解决我一直困扰的问题，就是在每一层递归时，怎么记住本次递归时使用的数尼，他巧妙的运用了数组来解决这个问题，每次递归遍历时就会开辟一个数组空间，记录本层已经使用的数，当下次再回到本层中时，如果本层之前的数与当前正在递归遍历的数相同的时候，说明这个数不需要递归了，如果递归，集合就会有重复的子集合，不满足题目结果。从而就这样解决了去重的问题。同时在每次遍历的时候开辟数组大小为多少合适尼，这就考虑到数组中绝对值最大的数是多少，我们就应该开辟最大数的2倍个存储空间个大小的数组（有负数存在，所以数组长度乘于二）,所在题目提示中指出数组中元素取值都在-100到100之间，所以在每层开辟数组的时候，开辟一个大小为201的数组(-100到100一共有201个数，记得0也算啊),那么我们怎么记录使用过的数尼，因为数组下标不能为负数，所以数组中每个数平移100位，这就能保证数组中所有的元素在正数的范围内。我们就拿移动后的元素作为下标，这样如果该位置没有使用，那么在本次遍历的时候，本层的构造数组该位置置为一，等到下次遍历的本层的时候，如果该位置已经是一的话，说明本层之前的元素于正在遍历的元素相等，就跳过本元素的递归，就能达到去重的效果。这样就解决了我的问题。 - 具体实现逻辑如下，每一步都有具体的解释。 4. 代码示例 ```java //最终结果集 List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> findSubsequences(int[] nums) { //调用子集写的递归回溯算法，求得最后结果 trackBack(0,nums,new ArrayList<>()); return result; } public void trackBack(int index,int[]nums,List<Integer> temp){ //如果遍历过程中子集的长度大于等于2,那么该子集可以加入最终结果集 if(temp.size()>=2){ result.add(new ArrayList<>(temp)); } //每一层构造一个大小位201的数组，记录本层元素的使用情况，达到去重的效果 int[]used = new int[200]; //对于本层元素逐一进行递归操作 for (int i = index; i < nums.length; i++) { //如果临时集合不为空，并且集合最后一个元素大于当前遍历的元素 //或者当前元素在本层之前已经被使用了， // 那就跳过该元素的递归，继续寻找下一个符合要求的元素 if((!temp.isEmpty() && nums[i] < temp.get(temp.size()-1)) || used[nums[i]+100]==1) { continue; } //否则就把该元素置为已经使用过 used[nums[i]+100]=1; //并且把该元素加入零时子序列集合中 temp.add(nums[i]); //继续向下执行 trackBack(i+1,nums,temp); //回溯到本层，移除之前添加的元素，使其在进入本层时的初始状态不能发生变化 temp.remove(temp.size()-1); } } ```
{{ item.content }}
{{ child.content }}