491.递增子序列
题目描述
给你一个整数数组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]]提示：
1 <= nums.length <= 15-100 <= nums[i] <= 100
代码
classSolution{// 存放最终结果List<List<Integer>>result=newArrayList<>();// 当前递归路径（当前子序列）List<Integer>path=newArrayList<>();/** * 回溯函数 * * @param nums 原数组 * @param startIndex 当前层开始搜索的位置 */publicvoidbacktracking(int[]nums,intstartIndex){// 题目要求子序列长度至少为2// 满足条件就加入结果集if(path.size()>1){result.add(newArrayList<>(path));}/** * 本层去重集合 * * 作用： * 同一树层中，相同数字只使用一次 * * 注意： * 这里不能使用全局 used[] * 因为本题不能排序， * 相同元素不一定相邻 */Set<Integer>used=newHashSet<>();// 横向遍历（树层）for(inti=startIndex;i<nums.length;i++){/** * 剪枝1：树层去重 * * 如果当前数字在本层已经使用过， * 则跳过，避免重复结果 */if(used.contains(nums[i]))continue;/** * 剪枝2：保证递增 * * 如果当前数字小于路径最后一个数字， * 则不满足递增条件 */if(!path.isEmpty()&&nums[i]<path.get(path.size()-1)){continue;}// 本层标记已使用used.add(nums[i]);// 做选择path.add(nums[i]);// 递归下一层backtracking(nums,i+1);// 回溯：撤销选择path.remove(path.size()-1);}}publicList<List<Integer>>findSubsequences(int[]nums){// 从下标0开始搜索backtracking(nums,0);returnresult;}}
