1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
private List<List<Integer>> ans;
public List<List<Integer>> findSubsequences(int[] nums) {
ans = new ArrayList<>();
backtrack(new ArrayList<>(), nums, 0);
return ans;
}
private void backtrack(List<Integer> currComb, int[] nums, int ptr) {
Set<Integer> used = new HashSet<>();
for (int i = ptr; i < nums.length; i++) {
if (!used.contains(nums[i]) && (currComb.isEmpty() || nums[i] >= currComb.get(currComb.size() - 1))) {
currComb.add(nums[i]);
if (currComb.size() > 1) {
ans.add(new ArrayList<>(currComb));
}
backtrack(currComb, nums, i + 1);
currComb.remove(currComb.size() - 1);
used.add(nums[i]);
}
}
}
}
|
我们用一个list来装non-decreasing sequence.首先是sequence第0个元素, nums中从0到最后一个元素都可以做, 然后是找第1个元素, 第一个元素的候选数需要是第0个元素在nums中index之后. 然后是第2个元素…
这么看来就是backtrack的典型特征.在sequence的某个位置, 相同数字不能重复坐拥这个位置. 于是我们使用一个local set来去存储当前位置有哪些数字坐过, 坐过的之后就不能再做了. 一个函数栈桢就代表sequence中的一个位置, 因此local set就可以用来记录在sequence的当前位置上哪些数字在这里坐过.
时间复杂度和空间复杂度不会搞.
