Code & Func

第27天

今天的题目是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:

1
[
2
  [3],
3
  [1],
4
  [2],
5
  [1,2,3],
6
  [1,3],
7
  [2,3],
8
  [1,2],
9
  []
10
]

我的做法是用递归的方法去做:

1
vector<vector<int>> subsets(vector<int>& nums) {
2
    vector< vector<int> > ret;
3
    vector<int> vec;
4
    ret.push_back(vec);
5
    subsetsIter(ret,nums,vec,0);
6
    return ret;
7
}
8

9
void subsetsIter(vector< vector<int> > &ret,vector<int> &nums,vector<int> now,int beg) {
10
    //if (now.size() == nums.size()) return ;
11
    now.push_back(-1);
12
    auto rbeg = now.rbegin();
13
    for(int i = beg;i < nums.size();i++) {
14
        *rbeg = nums[i];
15
        ret.push_back(now);
4 collapsed lines
16
        subsetsIter(ret,nums,now,i+1);
17
    }
18
    now.pop_back();
19
}

然后是在dicuss中看到的迭代的方法和利用二进制的方法：

1
vector<vector<int>> subsets(vector<int>& nums) {
2
    sort(nums.begin(), nums.end());
3
    vector<vector<int>> subs(1, vector<int>());
4
    for (int i = 0; i < nums.size(); i++) {
5
        int n = subs.size();
6
        for (int j = 0; j < n; j++) {
7
            subs.push_back(subs[j]);
8
            subs.back().push_back(nums[i]);
9
        }
10
    }
11
    return subs;
12
}

1
vector<vector<int>> subsets(vector<int>& nums) {
2
    sort(nums.begin(), nums.end());
3
    int num_subset = pow(2, nums.size());
4
    vector<vector<int> > res(num_subset, vector<int>());
5
    for (int i = 0; i < nums.size(); i++)
6
        for (int j = 0; j < num_subset; j++)
7
            if ((j >> i) & 1)
8
                res[j].push_back(nums[i]);
9
    return res;
10
}