78. Subsets

O(n!) time

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res{{}};
        for (int x : nums) {
            for (int i = size(res) - 1; i >= 0; --i) { // 一定要用n，不能动态取值
                res.push_back(res[i]);
                res.back().push_back(x);
            }
        }
        return res;
    }
};

backtracking

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }

    void dfs(const vector<int> &A, int b) {
        res.push_back(v);
        for (int i = b; i < size(A); ++i) {
            v.push_back(A[i]);
            dfs(A, i + 1);
            v.pop_back();
        }
    }

    vector<int> v;
    vector<vector<int>> res;
};