lintcode:Subsets

Given a set of distinct integers, return all possible subsets.

Challenge
Can you do it in both recursively and iteratively?

1.18s

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsets(vector<int> &nums) {
        // write your code here
        int len=nums.size();
        vector<vector<int> >res;

        int sum=1<<len;
        for(int i=0;i<sum;i++){
            vector<int> sub;
            for(int j=0;j<len;j++){
                if(i&(1<<j)){
                    sub.push_back(nums[len-1-j]);
                }
            }
            reverse(sub.begin(),sub.end());
            res.push_back(sub);
        }

        return res;
    }
};

2.21s

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > res;

    void dfs(vector<int> &nums, vector<bool> &choosed, int cur){
        if(cur==nums.size()){
            vector<int> sub;
            for(int i=0;i<choosed.size();i++){
                if(choosed[i]){
                    sub.push_back(nums[i]);
                }
            }
            res.push_back(sub);
            return;
        }

        choosed[cur]=true;
        dfs(nums,choosed,cur+1);
        choosed[cur]=false;
        dfs(nums,choosed,cur+1);
    }

    vector<vector<int> > subsets(vector<int> &nums) {
        // write your code here
        vector<bool> choosed(nums.size(),false);

        dfs(nums,choosed,0);

        return res;
    }
};