LeetCode78 子集

前言

题目： 78. 子集
文档： 代码随想录——子集
编程语言： C++
解题状态： 差一点…

思路

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

代码

class Solution {
private:vector<vector<int>> res;vector<int> path;void backtracking(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]);backtracking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {res.clear();path.clear();backtracking(nums, 0);return res;}
};

• 时间复杂度： $O(n\ast 2^n)$
• 空间复杂度： $O(n)$