题目
给你一个整数数组 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]]
解题
if(i>startIndex&&nums[i]==nums[i-1]) continue;//只能去除连续的，如果出现[1,2,3,2,1]这种例子就不行了,会出现两次[1,2],之前的例子中是因为可以排序，但是这个题不行
通过uset要确定 当前 横向(for) 有无出现过相同的数字，来去重。
class Solution { public: vector<vector<int>> res; vector<int> path; void backtracing(vector<int>& nums,int startIndex){ if(path.size()>=2){ res.push_back(path); } unordered_set<int> uset; for(int i=startIndex;i<nums.size();i++){ if((!path.empty()&&nums[i]<path.back())||uset.find(nums[i])!=uset.end()){ continue; } uset.insert(nums[i]); path.push_back(nums[i]); backtracing(nums,i+1); path.pop_back(); } } vector<vector<int>> findSubsequences(vector<int>& nums) { backtracing(nums,0); return res; } };
换种写法
class Solution { public: vector<vector<int>> res; vector<int> path; void backtracing(vector<int>& nums,int startIndex){ if(path.size()>=2){ res.push_back(path); } unordered_set<int> uset; for(int i=startIndex;i<nums.size();i++){ if((path.empty()||!path.empty()&&nums[i]>=path.back())&&uset.count(nums[i])==0) { uset.insert(nums[i]); path.push_back(nums[i]); backtracing(nums,i+1); path.pop_back(); } } } vector<vector<int>> findSubsequences(vector<int>& nums) { backtracing(nums,0); return res; } };
java
class Solution { List<List<Integer>> res=new LinkedList<>(); List<Integer> path=new LinkedList<>(); void dfs(int[] nums,int startIndex){ if(path.size()>=2){ res.add(new LinkedList<>(path)); } Set<Integer> set=new HashSet<>(); for(int i=startIndex;i<nums.length;i++){ if((path.isEmpty()||!path.isEmpty()&&nums[i]>=path.get(path.size()-1))&&set.contains(nums[i])==false){ set.add(nums[i]); path.add(nums[i]); dfs(nums,i+1); path.remove(path.size()-1); } } } public List<List<Integer>> findSubsequences(int[] nums) { dfs(nums,0); return res; } }
