[Recursion and Dynamic Programming] interview questions #4

[rygh4775]

Power Set: Write a method to return all subsets of a set.

[RoyMoon]

Solution 1 : backTracking

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subs;
        vector<int> sub;
        subsets(nums, 0, sub, subs);
        return subs;
    }
private:
    void subsets(vector<int>& nums, int i, vector<int>& sub, vector<vector<int>>& subs) {
        subs.push_back(sub);
        for (int j = i; j < nums.size(); j++) {
            sub.push_back(nums[j]);
            subsets(nums, j + 1, sub, subs);
            sub.pop_back();
        }
    }
};

output : [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

solution 2 : Iterative

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subs = {{}};
        for (int num : nums) {
            int n = subs.size();
            for (int i = 0; i < n; i++) {
                subs.push_back(subs[i]); 
                subs.back().push_back(num);
            }
        }
        return subs;
    }
}; 

input : [1,2,3] output : [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Initially, one empty subset [[]] Adding 1 to []: [[], [1]]; Adding 2 to [] and [1]: [[], [1], [2], [1, 2]]; Adding 3 to [], [1], [2] and [1, 2]: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].