Given a set of distinct integers, nums, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- 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],
[]
]
思路:由于nums中每个数字都没有重复,因此该数字只有出现或不出现两种情况。
这道题有三种方法来做。第一种是用dfs来遍历每一种情况。
1 class Solution { 2 public: 3 void help(vector<vector<int> >& res, vector<int>& nums, vector<int> cand, int cur) 4 { 5 if (cur == nums.size()) 6 { 7 res.push_back(cand); 8 return; 9 } 10 help(res, nums, cand, cur + 1); 11 cand.push_back(nums[cur]); 12 help(res, nums, cand, cur + 1); 13 } 14 vector<vector<int>> subsets(vector<int>& nums) { 15 sort(nums.begin(), nums.end()); 16 vector<vector<int> > res; 17 vector<int> cand; 18 help(res, nums, cand, 0); 19 return res; 20 } 21 };
第二种方法,用位运算。每一位表示nums数组中的一个数字是否出现。
1 class Solution { 2 public: 3 vector<vector<int>> subsets(vector<int>& nums) { 4 int tot = 1 << nums.size(); 5 vector<vector<int> > res; 6 sort(nums.begin(), nums.end()); 7 for (int i = 0; i < tot; i++) 8 { 9 vector<int> tem; 10 for (int j = 0; (1 << j) <= i; j++) 11 if ((1 << j) & i) 12 tem.push_back(nums[j]); 13 res.push_back(tem); 14 } 15 return res; 16 } 17 };
第三种是迭代。依次枚举每一个位置的数字,将其加到当前已有的所有子集的最后作为新的子集。
1 class Solution { 2 public: 3 vector<vector<int>> subsets(vector<int>& nums) { 4 sort(nums.begin(), nums.end()); 5 vector<vector<int>> subs(1, vector<int>()); 6 for (int i = 0; i < nums.size(); i++) { 7 int n = subs.size(); 8 for (int j = 0; j < n; j++) { 9 subs.push_back(subs[j]); 10 subs.back().push_back(nums[i]); 11 } 12 } 13 return subs; 14 } 15 };