10.非递减子序列
- 题目描述
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
示例 1：
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2：
输入：nums = [4,4,3,2,1]
输出：[[4,4]]
- 题目分析
本题由于是要求解递增子序列，由于所求序列有要求，所以在去重的时候我们不可以将nums先进行排序，再进行递归，这样会使得结果错误，此时我们该如何去重呢？
去重操作
通过上面可以看到，如果发生重复元素，那么它发生在同一树层，以4节点为例，当遍历完4是，需要将集合[7,6,7]依次与4组合，不难看出集合中存在两个7，这一定会造成元素重复，如果将集合变成[7,6]就可以避免这一问题，因此这里可以使用set来去重，这样就可以避免这样情况
Set<Integer> set = new HashSet<>(); // 用于记录当前路径中已经选择过的元素
完整思路
1.首先，我们定义了两个变量：path 和 result。path 是一个链表用于存储当前路径的元素，result 是一个列表用于存储最终的结果。
2.然后，我们定义了一个 findSubsequences 方法，该方法接受一个整数数组 nums 作为参数，并返回所有符合条件的递增子序列列表。在该方法内部，我们调用了 backtrack 方法开始搜索。
3.backtrack 方法是实现回溯的核心部分。它接受两个参数：nums 数组和 startIndex 起始位置。在该方法中，我们首先判断当前路径的长度是否大于1，如果是，说明找到了一个符合条件的递增子序列，将其添加到 result 列表中。
4.然后，我们创建一个 Set<Integer> 集合来记录当前路径中已经选择过的元素，以避免重复选择。接着，我们使用一个循环从 startIndex 开始遍历数组 nums，对于每个元素，如果它已经在路径中存在，或者小于路径末尾元素，则跳过，保证递增性。
5.如果当前元素满足条件，我们将其添加到路径中，同时将其添加到已选择元素的集合中。然后，递归调用 backtrack 方法，将起始位置更新为 i+1，继续搜索下一层。
6.当递归结束后，我们需要将当前元素从路径中移除，以尝试其他可能的组合。
- Java代码实现
LinkedList<Integer> path = new LinkedList<>(); // 用于存储当前路径的集合
List<List<Integer>> result = new ArrayList<>(); // 用于存储最终结果的列表
/**
* 寻找数组中长度大于等于2的递增子序列
* @param nums 给定的整数数组
* @return 所有符合条件的递增子序列列表
*/
public List<List<Integer>> findSubsequences(int[] nums) {
backtrack(nums, 0); // 调用回溯函数开始搜索
return result; // 返回最终结果
}
/**
* 回溯函数，用于搜索所有可能的递增子序列
* @param nums 给定的整数数组
* @param startIndex 当前搜索的起始位置
*/
private void backtrack(int[] nums, int startIndex) {
if (path.size() > 1) {
result.add(new ArrayList<>(path)); // 如果当前路径长度大于1，则将该路径加入最终结果
}
Set<Integer> set = new HashSet<>(); // 用于记录当前路径中已经选择过的元素
for (int i = startIndex; i < nums.length; i++) {
if (set.contains(nums[i]) || (!path.isEmpty() && nums[i] < path.get(path.size() - 1))) {
continue; // 如果当前元素已经在路径中或者小于路径末尾元素，则跳过，保证递增性
}
path.add(nums[i]); // 将当前元素加入路径
set.add(nums[i]); // 将当前元素添加到已选择元素的集合中
backtrack(nums, i + 1); // 递归调用下一层搜索，更新起始位置为 i+1
path.removeLast(); // 移除当前元素，尝试其他可能的组合
}
}
- 代码疑点1：像之前回溯算法一样，set在添加完之后是否需要set.remove()回溯操作呢？
这里是不需要的，因为set处理的逻辑是每一个树层，当遍历同一树层时，即for (int i = startIndex; i < nums.length; i++)，此时set要记录这一树层所有的点，因此不需要set.remove()回溯操作，又因为set为局部变量，因此也不会影响其他树层的去重操作
- **代码疑点2：**判断是否递增怎么做？
我们判断递增子序列，只要知道子序列最后一个元素和当前元素的大小关系就可以了
!path.isEmpty() && nums[i] < path.get(path.size() - 1))
nums[i]：当前元素
path.get(path.size() - 1))：子序列最后一个元素
