Subsets

Subsets I:

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],
  []
]

New Version: we can find that if we have the subsets of N-1 numbers, then the result is composed of adding the Nth number to each of the subsets of N-1 numbers plus the original subsets of N-1 numbers, i.e. S(N) = S(N-1) + (adding N to S(N-1)).

Runtime: 4ms

 1 class Solution {
 2 public:
 3     vector<vector<int>> subsets(vector<int>& nums) {
 4         vector<vector<int> > result;
 5         if(nums.empty()) return result;
 6         
 7         sort(nums.begin(), nums.end());
 8         vector<int> temp;
 9         
10         //manipulate the first number in nums
11         result.push_back(temp);
12         temp.push_back(nums[0]);
13         result.push_back(temp);
14         int level = 1;
15         
16         //manipulate the remaining numbers in nums
17         while(level < nums.size()){
18             int n = result.size();
19             for(int i = 0; i < n; i++){
20                 temp = result[i];
21                 temp.push_back(nums[level]);
22                 result.push_back(temp);
23             }
24             level++;
25         }
26         
27         return result;
28     }
29 };

Analyse: Each number has two states: selected or not selected. Recursively invoke the choose function until the step equals to the size. Then construct a vector to store all selected numbers, and push it to the result vector.

Runtime: 8ms.

 1 class Solution {
 2 public:
 3     vector<vector<int>> subsets(vector<int>& nums) {
 4         vector<vector<int> > result;
 5         sort(nums.begin(), nums.end());
 6         vector<bool> selected(nums.size(), false);
 7         subset(nums, selected, 0, result);
 8         
 9         return result;
10     }
11     
12     void subset(vector<int> &nums, vector<bool> &selected, int step, vector<vector<int> > &result){
13         if(step == nums.size()){
14             vector<int> temp;
15             for(int i = 0; i < step; i++){
16                 if(selected[i]) temp.push_back(nums[i]);
17             }
18             result.push_back(temp);
19             return;
20         }
21         
22         //not choose the number
23         selected[step] = false;
24         subset(nums, selected, step + 1, result);
25         //choose the number
26         selected[step] = true;
27         subset(nums, selected, step + 1, result);
28     }
29 };

Subsets II:

Given a collection of integers that might contain duplicates, 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,2], a solution is:

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

Analyse: It is the same as subsets I except that we need to set a variable keep the place where we start to push the last number.

Runtime: 12ms

 1 class Solution {
 2 public:
 3     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
 4         vector<vector<int> > result;
 5         if(nums.empty()) return result;
 6         
 7         sort(nums.begin(), nums.end());
 8         vector<int> temp;
 9         
10         //manipulate the first number in the nums
11         result.push_back(temp);
12         temp.push_back(nums[0]);
13         result.push_back(temp);
14         int level = 1;
15         int index = 1; //the place where push the first number
16         
17         //manipulate remaining numbers in the nums
18         while(level < nums.size()){
19             int i;
20             if(nums[level] == nums[level - 1])
21                 i = index;
22             else i = 0;
23             index = result.size();
24             int n = result.size();
25             for(; i < n; i++){
26                 temp = result[i];
27                 temp.push_back(nums[level]);
28                 result.push_back(temp);
29             }
30             level++;
31         }
32         return result;
33     }
34 };