78. Subsets

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

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

S1：　DFS

可以处理有重复数字的情况，对于这题distinct num这种解法不必要

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> subset;
        sort(nums.begin(), nums.end());
        dfs(nums, 0, subset, result);
        return result;
    }

    void dfs(vector<int>& nums, int start, vector<int> subset, vector<vector<int>>& result) {
        if (start == nums.size()) {
            result.push_back(subset);
            return;
        }
        int count = 0;
        for (int i = start; i < nums.size() && nums[i] == nums[start]; ++i) {
            count++;
        }
        dfs(nums, start + count, subset, result);
        for (int i = 0; i < count; ++i) {
            subset.push_back(nums[start]);
            dfs(nums, start + count, subset, result);
        } 
    }
};

S2: bit manipulation

因为数字distinct, 可用长为2^n - 1的int每一位的1，0来表示每个数在subset出现的情况

    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> result;
        int digitLen = pow(2, n) - 1;
        for (int i = 0; i <= digitLen; ++i) {
            vector<int> subset;
            for (int idx = 0; idx < n; ++idx) {
                if(i >> idx & 1) {
                    subset.push_back(nums[idx]);
                }
            }
            result.push_back(subset);
        }
        return result;
    }