Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

AC代码

void deal(vector<int>& nums, int k, vector<vector<int>>& ans, map<int, int>& mp) {
    vector<int> v;
    int i = 0;
    while (true) {
        if (i == nums.size()) {
            if (v.empty()) break;
            else {
                i = mp[v[v.size() - 1]] + 1;
                v.pop_back();
            }
        }
        else if (v.size() != k) 
            v.push_back(nums[i++]);        
        if (v.size() == k) {
            ans.push_back(v);
            v.pop_back();
        }
    }
}

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans{{}};
        map<int, int> mp;
        for (int i = 0; i < nums.size(); ++i) mp[nums[i]] = i;
        for (int i = 0; i < nums.size(); ++i) deal(nums, i + 1, ans, mp);
        return ans;
    }
};

另解1

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

另解2（递归）

void digui(int idx, vector<int> nums, vector<int>& v,
           vector<vector<int>>& res) {
    if (idx == nums.size()) {
        res.push_back(v);
        return;
    }
    digui(idx + 1, nums, v, res);
    v.push_back(nums[idx]);
    digui(idx + 1, nums, v, res);
    v.pop_back();
}

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

另解3

vector<int> createSub(vector<int>& nums, int i) {
    vector<int> v;
    int idx = 0;
    while (i != 0) {
        if (i & 1) {
            v.push_back(nums[idx]);
        }
        idx++;
        i >>= 1;
    }
    return v;
}

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int k = 1 << nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i < k; i++) {
            vector<int> v = createSub(nums, i);
            ans.push_back(v);
        }
        return ans;
    }
};

总结

自己的思路是从77题中学的，另解参考：https://www.cnblogs.com/grandyang/p/4309345.html