LeetCode--491.递增子序列（回溯算法）
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{// 存放最终结果ListListIntegerresultnewArrayList();// 当前递归路径当前子序列ListIntegerpathnewArrayList();/** * 回溯函数 * * param nums 原数组 * param startIndex 当前层开始搜索的位置 */publicvoidbacktracking(int[]nums,intstartIndex){// 题目要求子序列长度至少为2// 满足条件就加入结果集if(path.size()1){result.add(newArrayList(path));}/** * 本层去重集合 * * 作用 * 同一树层中相同数字只使用一次 * * 注意 * 这里不能使用全局 used[] * 因为本题不能排序 * 相同元素不一定相邻 */SetIntegerusednewHashSet();// 横向遍历树层for(intistartIndex;inums.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,i1);// 回溯撤销选择path.remove(path.size()-1);}}publicListListIntegerfindSubsequences(int[]nums){// 从下标0开始搜索backtracking(nums,0);returnresult;}}
)
