给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例:
1
2
| 输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
|
说明:
- 给定数组的长度不会超过15。
- 数组中的整数范围是 [-100,100]。
- 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
我们可以枚举出所有的子序列，然后判断当前的子序列是否是非严格递增的。对于数组中的每个数来说都有选中和不选中两种状态。长度为 n 的序列选择子序列一共有 2 ^ n 种情况。我们可以使用递归的方法实现二进制枚举，然后判断是否合法，我们可以得到这样的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
public void dfs(int cur, int[] nums) {
if (cur == nums.length) {
if (isValid() && notVisited()) {
ans.add(new ArrayList<Integer>(temp));
}
return;
}
temp.add(nums[cur]);
dfs(cur + 1, nums);
temp.remove(temp.size() - 1);
dfs(cur + 1, nums);
}
|
用一个临时数组 temp 保存当前选出的子序列，用 cur 来表示当前位置的下标，在 执行dfs(cur, nums)之前，[0, cur - 1]区间内的所有元素都被考虑过，[cur, n]区间内的元素还未被考虑。我们考虑 cur 位置选或者不选，如果选择当前元素，将当前元素加入 temp，然后递归下一个位置，在递归结束后，把 temp 的最后一个元素删除进行回溯；如果不选择当前元素，直接递归下一个位置。
我们可以对选择和不选择做一些简单的限定，就可以让枚举出来的序列都是合法且不重复：
只有当前的元素大于等于上一个选择的元素时才能选择这个元素，这样枚举出来的所有元素都是合法的。
如何保证没有重复呢？我们给不选择做一个限定条件，只有当当前的元素不等于上一个选择的元素的时候，才考虑不选择当前元素，直接递归后面的元素。如果有两个相同的元素，我们有四种情况:
- 选前者，选后者
- 选前者，不选后者
- 不选前者，选后者
- 不选前者，不选后者
其中第二种和第三种情况是等价的，这样限制后，舍弃了第二种，保留了第三种。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
List<Integer> temp = new ArrayList<>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> findSubsequences(int[] nums) {
dfs(0, Integer.MIN_VALUE, nums);
return ans;
}
public void dfs(int cur, int last, int[] nums){
if(cur == nums.length){
if(temp.size() >= 2){
ans.add(new ArrayList<Integer>(temp));
}
return;
}
if(nums[cur] >= last){
temp.add(nums[cur]);
dfs(cur + 1, nums[cur], nums);
temp.remove(temp.size() - 1);
}
if(nums[cur] != last){
dfs(cur + 1, last, nums);
}
}
}
|
时间复杂度O(n * 2 ^ n)，枚举子序列O(2 ^ n)，保存答案O(n)。
空间复杂度O(n)。