public class Solution {
public List<List<Integer>> findSubsequences(int[] nums) {
Set<List<Integer>> res= new HashSet<List<Integer>>();
List<Integer> holder = new ArrayList<Integer>();
findSequence(res, holder, 0, nums);
List result = new ArrayList(res);
return result;
}
public void findSequence(Set<List<Integer>> res, List<Integer> holder, int index, int[] nums) {
if (holder.size() >= 2) {
res.add(new ArrayList(holder));
}
for (int i = index; i < nums.length; i++) {
if(holder.size() == 0  holder.get(holder.size()  1) <= nums[i]) {
holder.add(nums[i]);
findSequence(res, holder, i + 1, nums);
holder.remove(holder.size()  1);
}
}
}
}
Java 20 lines backtracking solution using set, beats 100%.


Thanks for sharing. I have very similar idea to yours, it's just I don't use a Set to avoid duplicated result, but my code cannot pass a long case ( [1,2,3,4,5,6,7,8,9,10,1,1,1,1,1] ), I have no idea about the problem. Any suggestions?
public class Solution { private void helper(int[] nums, int index, List<Integer> buffer, List<List<Integer>> result){ if( buffer.size()>=2 ) result.add( new ArrayList<Integer>(buffer) ); for(int i=index; i<nums.length; i++){ if( buffer.size()==0  nums[i]>=buffer.get(buffer.size()1) ){ buffer.add(nums[i]); helper(nums, i+1, buffer, result); buffer.remove(buffer.size()1); } while(i+1<nums.length && nums[i]==nums[i+1]) i++; } } public List<List<Integer>> findSubsequences(int[] nums) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if(nums.length<2) return result; helper(nums, 0, new ArrayList<Integer>(), result); return result; } }

@mycoy
I tried with smaller input i.e. [1,2,3,2] and your code fails, it adds duplicate.
your output : [[1,2],[1,2,3],[1,2,2],[1,3],[1,2],[2,3],[2,2]]
Expected : [[1,2],[2,2],[1,3],[2,3],[1,2,3],[1,2,2]]In yours [1,2] is repeated twice and to avoid this I have maintained a set.
With the while loop you are just checking if consecutive elements are same. If the test case is [1,2,2,3] your logic will work, but it will not when the repeated elements is not consecutive.

@adarshkp said in Java 20 lines backtracking solution using set, beats 100%.:
[1,2,3,2]
Thanks for pointing out my problem. You're correct, my code cannot handle cases like, [1,2,3,2]; I didn't understand that point well.


@mycoy we cannot use Arrays.sort() (according to the probelm), so the same elements are not gathered togather(adjacent), so we cannot use "if(i != index && array[i1] == array[i]) continue;" to deduplicate

Thanks for sharing! I also have similar idea, but I am still look for solution that does not use hashset to avoid duplicates. Does anyone have some idea?
public List<List<Integer>> findSubsequences(int[] nums) { Set<List<Integer>> res = new HashSet<List<Integer>>(); for(int i = 0; i < nums.length  1; i ++){ dfs(res, new ArrayList<Integer>(), nums, i, Integer.MIN_VALUE); } return new ArrayList(res); } public void dfs(Set<List<Integer>> res, List<Integer> cur, int[] nums, int start, int pre){ if(cur.size() > 1){ res.add(new ArrayList<Integer>(cur)); } for(int i = start; i < nums.length; i ++){ if(nums[i] < pre) continue; cur.add(nums[i]); int tmp = pre; dfs(res, cur, nums, i + 1, nums[i]); pre = tmp; cur.remove(cur.size()  1); } }

@mycoy Because input array is not sorted, you way to avoid duplication is only working for sorted array.

@mycoy even using arraylist.contains() method to avoid the duplicate elements, you will still get a time limit error. my suggest is using a set instead, it only takesO (1) to check the repeated element

Thanks for sharing! This problem is similar to Subset II. So at first it seems same techniques ("Arrays.sort(nums)" first then bypass duplicate by "i > start && nums[i] == nums[i1]") could be in use. Then I realize that I miss the key requirement of this problem: subsequence which means we cannot change original array. Then Set seems to be the only thing to resort.

Same idea, a slight difference is pass the min value for the next recursive call instead of using the last element in path.
public class Solution { Set<List<Integer>> ans = new HashSet<>(); public List<List<Integer>> findSubsequences(int[] nums) { helper(nums, 0, Integer.MIN_VALUE, new ArrayList<Integer>()); return new ArrayList<List<Integer>>(ans); } public void helper(int[] nums, int idx, int min, ArrayList<Integer> path) { if (path.size() >= 2) { ans.add(new ArrayList<Integer>(path)); } for (int i = idx; i < nums.length; ++i) { if (nums[i] >= min) { path.add(nums[i]); helper(nums, i + 1, nums[i], path); path.remove(path.size()  1); } } } }

@adarshkp
I used set to store popped items instead of sets. I think it is slightly more efficient.
void findHelper(vector<int>& tmp, int i, vector<vector<int>>& res, vector<int>& nums) {if (tmp.size() > 1) res.push_back(tmp); unordered_set<int> popped; for (int j = i; j < nums.size(); j++) { if (!tmp.empty() && tmp.back() > nums[j]) continue; if(popped.find(nums[j]) != popped.end()) continue; tmp.push_back(nums[j]); findHelper(tmp, j + 1, res, nums); tmp.pop_back(); popped.insert(nums[j]); }
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<int> tmp; vector<vector<int>> res; findHelper(tmp, 0, res, nums); return res;
}

A possible improvement: instead of using a global set to remove duplication in the final results, we can maintain a local set at each step. The principle is that at each step, a new value can only be picked once.
The advantage of a local set is that it can filter out the potential repetitions just at the beginning instead of at the end of a subsequence building. For example,
[1, 1, 9, 3, 6]
. With a global set, we have to filter all the sequences starting at the 2nd 1 since they will certainly duplicate with the results beginning with the 1st 1. However, with a local set, at the first step, we will only choose the 1st 1 for sequence building and the 2nd 1 is excluded just at the first step.Of course a local set at each step will lead to extra costs. However, I think it can improve the efficiency in general, especially for an array with many repetitions, such as
[1, 1, 1, 1, 1, 1, 3]
.class Solution(object): def findSubsequences(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ self.r = [] self.path = [] self.nums = nums self.backtrack(0) return self.r def backtrack(self, i): # choose next number starting from the index i if i == len(self.nums): return # for j in index range [i, len), if nums[j] >= last in the # path and its value has not been used at this step, then use it s = set() # check possible repetitions of this step for j in range(i, len(self.nums)): if (not self.path or self.nums[j] >= self.path[1]) and (self.nums[j] not in s): s.add(self.nums[j]) self.path.append(self.nums[j]) # a new value is appended if len(self.path) >= 2: self.r.append(list(self.path)) self.backtrack(j + 1) del self.path[1] # restore the state