[LeetCode] Subsets

简介: Recursive (Backtracking) This is a typical problem that can be tackled by backtracking. Since backtracking has a more-or-less similar template, so I do not give explanations for this method.

Recursive (Backtracking)

This is a typical problem that can be tackled by backtracking. Since backtracking has a more-or-less similar template, so I do not give explanations for this method.

 1 class Solution {
 2 public:
 3     vector<vector<int>> subsets(vector<int>& nums) {
 4         sort(nums.begin(), nums.end());
 5         vector<vector<int>> subs;
 6         vector<int> sub;
 7         genSubsets(nums, 0, sub, subs);
 8         return subs; 
 9     }
10     void genSubsets(vector<int>& nums, int start, vector<int>& sub, vector<vector<int>>& subs) {
11         subs.push_back(sub);
12         for (int i = start; i < nums.size(); i++) {
13             sub.push_back(nums[i]);
14             genSubsets(nums, i + 1, sub, subs);
15             sub.pop_back();
16         }
17     }
18 };

Iterative

This problem can also be solved iteratively. Take [1, 2, 3] in the problem statement as an example. The process of generating all the subsets is like:

  1. Initially: [[]]
  2. Adding the first number to all the existed subsets: [[], [1]];
  3. Adding the second number to all the existed subsets: [[], [1], [2], [1, 2]];
  4. Adding the third number to all the existed subsets: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].

Have you got the idea :-)

The code is as follows.

 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 };

Bit Manipulation

This is the most clever solution that I have seen. The idea is that to give all the possible subsets, we just need to exhaust all the possible combinations of the numbers. And each number has only two possibilities: either in or not in a subset. And this can be represented using a bit.

There is also another a way to visualize this idea. That is, if we use the above example, 1appears once in every two consecutive subsets, 2 appears twice in every four consecutive subsets, and 3 appears four times in every eight subsets, shown in the following (initially the 8subsets are all empty):

[], [], [], [], [], [], [], []

[], [1], [], [1], [], [1], [], [1]

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

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

The code is as follows.

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

Well, just a final remark. For Python programmers, this may be an easy task in practice since the itertools package has a function combinations for it :-) 

目录
相关文章
LeetCode 90. Subsets II
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
51 0
LeetCode 90. Subsets II
|
2天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
2天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
2天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
2天前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板