[recommend for beginners]clean C++ implementation with detailed explanation


  • 2
    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            vector<vector<int>> result;
            vector<int> cur;
            help(result, cur, nums, 0);
            return result;
        }
        
        void help(vector<vector<int>> &result, vector<int> cur, vector<int>& nums, int pos){
            if(pos==nums.size()){
                if(cur.size()==0)   { result.push_back(cur); return; }
                sort(cur.begin(), cur.end());
                result.push_back(cur);
                return;
            }
            /*** skip ***/
            help(result, cur, nums, pos+1);
            /*** no skip ***/
            cur.push_back(nums[pos]);
            help(result, cur, nums, pos+1);
        }
    };

  • 1
    /*** dfs method ***/
    void help_dfs(vector<int>& nums, int start, vector<int>& cur, vector<vector<int>>& result){
        result.push_back(cur);
        for(int i=start; i<nums.size(); i++){
            cur.push_back(nums[i]);
            help_dfs(nums, i+1, cur, result);
            cur.pop_back();
        }
    }

  • 1
    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> subs(1, vector<int>());
            for(int i=0; i<nums.size(); i++){
                int n=subs.size();
                for(int j=0; j<n; j++){
                    subs.push_back(subs[j]);
                    subs.back().push_back(nums[i]);
                }
            }
            return subs;
        }
    };

  • 1
    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            int num_subset=pow(2, nums.size());
            vector<vector<int>> res(num_subset, vector<int>());
            for(int i=0; i<nums.size(); i++){
                for(int j=0; j<num_subset; j++){
                    if((j>>i)&1)  res[j].push_back(nums[i]);
                }
            }
            return res;
        }
    };

  • 0
    F
    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            int num_subset=pow(2, nums.size());
            vector<vector<int>> res(num_subset, vector<int>());
            for (int i = 0; i < num_subset; i++) {
                for (int j = 0; j < nums.size(); j++) {
                    if ((i>>j)&1)  res[i].push_back(nums[j]);
                }
            }
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.