Leetcode|子集|78. 子集（回溯+first索引）

1 回溯法

代码语言：javascript复制

class Solution {
private:
    int size;
    vector<vector<int>> solution;
    vector<int> path;
public:
    void backtrack(vector<int>& nums, int first) {
        solution.emplace_back(path);
        for (int i = first; i < size; i  ) {
            path.emplace_back(nums[i]);
            backtrack(nums, i   1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        size = nums.size();
        backtrack(nums, 0);
        return solution;
    }
};

2 数学归纳法（内存超时）

简而言之，就是[1, 2, 3]包含[1, 2]的子集，通过递归实现。但时间复杂度过高，为 O(N⋅2N)，因此我在力扣上提交也显示内存超时，但为了学习还是把代码放出来

代码语言：javascript复制

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        if (nums.empty()) return {{}};
        int data = nums.back();
        nums.pop_back();
        vector<vector<int>> solution = subsets(nums);
        for (int i = 0; i < solution.size(); i  ) {
            solution.emplace_back(solution[i]);
            solution.back().emplace_back(data);
        }
        return solution;
    }
};

递归 内存 数学

0 人点赞