1.题目

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：
输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示：
1 <= nums.length <= 15
-100 <= nums[i] <= 100

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/increasing-subsequences

2.思路

（1）回溯
思路参考本题官方题解。

3.代码实现（Java）

//思路1————回溯
class Solution {
    
    // res 保存所有结果
    List<List<Integer>> res = new ArrayList<>();
    
    // track 用于记录回溯的路径
    List<Integer> track = new ArrayList<>();
    
    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums.length <= 1) {
            return res;
        }
        backtrack(nums, 0, Integer.MIN_VALUE);
        return res;
    }
    
    public void backtrack(int[] nums, int cur, int last) {
        //找到一组递增子序列
        if (cur == nums.length) {
            if (track.size() >= 2) {
                res.add(new ArrayList<Integer>(track));
            }
            return;
        }
        if (nums[cur] >= last) {
            track.add(nums[cur]);
            backtrack(nums, cur + 1,nums[cur]);
            track.remove(track.size() - 1);
        }
        if (nums[cur] != last) {
            backtrack(nums, cur + 1, last);
        }
    }
}
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
30
31
32
33
34
35