解题思路

题目要求子序列至少2个元素且递增，那么我们添加条件可以是当path中有两个元素的时候

使用哈希表记录当前层使用过的元素，若再次碰到直接continue

当nums[i] < path的最后一个元素时则continue

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        
        def backtracking(startIndex: int, path: list[int]) -> None:
            if len(path) >= 2:
                result.append(path.copy())
            uset = set()
            for i in range(startIndex, len(nums)):
                if path and nums[i] < path[-1]: continue
                if nums[i] in uset: continue
                path.append(nums[i])
                uset.add(nums[i])
                backtracking(i + 1, path)
                path.pop()


        backtracking(0, [])
        return result

C++

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 {
private:
    vector<vector<int>> result;
    vector<int>path;

    void backtracking(int startIndex, vector<int> &nums) {
        unordered_set<int> uset;

        if (path.size() > 1) result.push_back(path);

        for (int i = startIndex; i < nums.size(); ++i) {
            if (!path.empty() && nums[i] < path[path.size() - 1]) continue;
            if (uset.find(nums[i]) != uset.end()) continue;
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(i + 1, nums);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(0, nums);
        return result;
    }

};

Go

var result [][]int
var path []int
func findSubsequences(nums []int) [][]int {
    result = [][]int{}
    path = []int{}
    backtracking(0, nums)
    return result
}

func backtracking(startIndex int, nums []int) {
    if len(path) > 1 {
        t := make([]int, len(path))
        copy(t, path)
        result = append(result, t)
    }
    uset := make(map[int]bool)
    for i := startIndex; i < len(nums); i++ {
        if len(path) != 0 && nums[i] < path[len(path) - 1] {continue}
        if uset[nums[i]] == true {continue}
        path = append(path, nums[i])
        uset[nums[i]] = true
        backtracking(i + 1, nums)
        path = path[:len(path) - 1]
    }
}