计算机科学基础leetcode刷题回溯算法
Source
Edit
History

78. 子集

Problem: 78. 子集

Reference

78.子集

思路

传统的回溯算法。

  1. 不同之处

这里找的是子集，之前都是在叶子节点采集结果，就是return的时候，而寻找子集也就是每一个节点都要收集。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backTracing(vector<int>& nums, int startIndex) {
        res.push_back(path);
        if (startIndex >= nums.size()) {
            return;
        }
        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backTracing(nums,i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backTracing(nums,0);
        return res;
    }
};