---
# System prepended metadata

title: 0491. Increasing Subsequences
tags: [Leetcode, DFS, backtracking, Medium]

---

# 0491. Increasing Subsequences
###### tags: `Leetcode` `Medium` `backtracking` `DFS`
Link: https://leetcode.com/problems/increasing-subsequences/
## 思路
和[0040. Combination Sum II](https://hackmd.io/cOOug_AXSUeBnJKIjdF2IA)有点像 但这题的问题在于不能给nums排序
所以如果遇到[1,5,1,1] 就会有两个[1,1]出现((index 0, index 2), (index 2, index 3))
比较简单的解决办法就是把记录答案的list换成set
## Code
```java=
class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> ans = new HashSet<>();
        dfs(ans, new ArrayList<>(), nums, 0);
        return new ArrayList(ans);
    }
    private void dfs(Set<List<Integer>> ans, List<Integer> curr, int[] nums, int start){
        if(curr.size()>1) ans.add(new ArrayList<>(curr));
        for(int i=start; i<nums.length; i++){
            if(i>start && nums[i]==nums[i-1]) continue;
            if(curr.size()==0 || curr.get(curr.size()-1)<=nums[i]){
                curr.add(nums[i]);
                dfs(ans, curr, nums, i+1);
                curr.remove(curr.size()-1);
            }
        }
    }
}
```