# Clean 20ms solution

• ``````public List<List<Integer>> findSubsequences(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
helper(res, new ArrayList<Integer>(), nums, 0);
return res;
}

private void helper(List<List<Integer>> res, List<Integer> list, int[] nums, int id) {
if (list.size() > 1) res.add(new ArrayList<Integer>(list));
List<Integer> unique = new ArrayList<Integer>();
for (int i = id; i < nums.length; i++) {
if (id > 0 && nums[i] < nums[id-1]) continue; // skip non-increase
if (unique.contains(nums[i])) continue; // skip duplicate
helper(res, list, nums, i+1);
list.remove(list.size()-1);
}
}
``````

• @shawloatrchen you can also use set for unique check:

``````List<Integer> unique = new ArrayList<Integer>();
``````

to

``````Set<Integer> unique = new HashSet<>();
``````

and

``````		if (unique.contains(nums[i])) continue; // skip duplicate
``````

to

``````if(!unique.add(nums[i])) continue;
``````

• @yuhaowang001 yes, you're right

• Python version:

``````class Solution(object):
def findSubsequences(self, nums):
def helper(res, arr, nums, i):
if len(arr) > 1:
res.append(list(arr))
unique = []
for k in xrange(i, len(nums)):
if i > 0 and nums[k] < nums[i-1]:
continue
if nums[k] in unique:
continue
arr.append(nums[k])
unique.append(nums[k])
helper(res, arr, nums, k + 1)
arr.pop()

res = []
helper(res, [], nums, 0)
return res
``````

Javascript:

``````var findSubsequences = function(nums) {
var res = [];
helper(res, [], nums, 0);
return res;
};

var helper = function(res, list, nums, id) {
if(list.length > 1) res.push(list.slice());
var unique = [];
for(var i = id; i < nums.length; i++) {
if(id > 0 && nums[i] < nums[id-1]) continue;
if(unique.indexOf(nums[i]) >= 0) continue;
unique.push(nums[i]);
list.push(nums[i]);
helper(res, list, nums, i+1);
list.pop()
}
}
``````

• @shawloatrchen can you explain the code? Thank you.

• @bo28 said in Clean 20ms solution:

@shawloatrchen can you explain the code? Thank you.

He's using recursive DFS and keeping a count of the uniques to prevent duplicate processing only if the number is increasing

• How can that List<Integer> unique be used to prevent duplicate processing ?? I'm quite confused with that one. Thanks

For example, my c++ code below for

[4,6,7,7]

i is 0
i is 1
i is 2
i is 3
i is 3
7
i is 2
6
i is 3
i is 3
7
6
i is 1
4
i is 2
i is 3
i is 3
7
i is 2
6
4
i is 3
i is 3
7
6
4

``````class Solution {
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;

dfs(res, path, nums, 0);
return res;
}

void dfs(vector<vector<int>>& res, vector<int>& path, vector<int>& nums, int idx){
if (path.size()>1)
res.push_back(path);

unordered_set<int> unique;

for (int i=idx; i<nums.size(); i++){
if (idx>0&&nums[i]<nums[idx-1])
continue;
cout<<"i is ";
cout<< i<<endl;
for (auto u: unique)
cout<<u<<endl;

if (unique.count(nums[i]))
continue;

unique.insert(nums[i]);
path.push_back(nums[i]);
dfs(res, path, nums, i+1);
path.resize(path.size()-1);
}
}
``````

};

• @coder2 in each recursion, same value only use once,
for example [1,5,1],
the first recursion only considers 1 and 5, the last 1 is skipped.
in recursion [1] the next value can either 5 or 1 so we have [1, 5] and [1,1]
in recursion [5] the next option is only 1, but 1 < 5 , and size of [5] is less than 2.
So, the final answer is [1,5] and [1,1];

• [1,5,1] would work for the following code, but [4,6,7,7] won't. I'm still confused.

class Solution {
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;

``````dfs(res, path, nums, 0);
return res;
``````

}

void dfs(vector<vector<int>>& res, vector<int>& path, vector<int>& nums, int idx){
if (path.size()>1){
cout<<"path.size()>1, idx is ";
cout<< idx <<endl;

``````    cout<<"path contains "<<endl;
for (auto u: path)
cout<<u<<endl;

res.push_back(path);
}

unordered_set<int> unique;

for (int i=idx; i<nums.size(); i++){
if (idx>0&&nums[i]<nums[idx-1])
continue;
cout<<"i is ";
cout<< i<<endl;

cout<<"unique include "<<endl;
for (auto u: unique)
cout<<u<<endl;
/*
if (unique.count(nums[i])){
cout<<"unique contains ";
cout<< nums[i]<<endl;
continue;
}
*/

unique.insert(nums[i]);
path.push_back(nums[i]);
dfs(res, path, nums, i+1);
path.resize(path.size()-1);
}
``````

}
};

• @coder2 You code is accepted, why confusing

• very good dedup method

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.