Subsets

subsets.cpp

// Iteration
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> vv;
    vv.push_back(vector<int>());
    for(int i = 0; i < nums.size(); i++){
        int n = vv.size();
        for(int j = 0; j < n; j++){
            vector<int> v(vv[j]);
            v.push_back(nums[i]);
            vv.push_back(v);
        }
    }
    return vv;
}
// Recursion version 1, position starts with nums.size()-1
vector<vector<int>> subsets(vector<int>& nums) {
    return subsetsrec(nums, nums.size()-1);
}
vector<vector<int>> subsetsrec(vector<int>& nums, int n){
    if (n == -1){
        vector<vector<int>> vv;
        vv.push_back(vector<int>());
        return vv;
    }
    vector<vector<int>> vv = subsetsrec(nums, n-1);
    int size = vv.size();
    for(int i = 0; i < size; i++){
        vector<int> v(vv[i]);
        v.push_back(nums[n]);
        vv.push_back(v);
    }
    return vv;
}

// Recursion version 2, position starts with 0
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>>res{{}};
    helper(nums, 0, res);
    return res;
}
void helper(vector<int>& nums, int idx, vector<vector<int>>& res){
    if (idx == nums.size()) return;
    for (int i = res.size() - 1; i >= 0; --i){
        vector<int>cur(res[i]);
        cur.push_back(nums[idx]);
        res.push_back(cur);
    }
    helper(nums, idx+1, res);
}