Note
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
The solution set must not contain duplicate subsets.
Example
If S =
[1,2,3]
, a solution is:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
class Solution {
public:
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
vector<vector<int>> subsets(vector<int> &nums) {
vector<vector<int>> output;
sort(nums.begin(), nums.end());
output.push_back(vector<int>());
for(int n : nums) {
for(int i = output.size()-1; i >=0; i--) {
vector<int> current = output[i];
current.push_back(n);
output.push_back(current);
}
}
return output;
}
};
class Solution {
public:
void helper(vector<int> &nums, int start, vector<int> & tmp, vector<vector<int>> &ans) {
for(int i = start; i < nums.size(); i++) {
tmp.push_back(nums[i]);
ans.push_back(tmp);
helper(nums, i+1, tmp, ans);
tmp.pop_back();
}
}
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
vector<vector<int>> subsets(vector<int> &nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
vector<int> tmp;
helper(nums, 0, tmp, ans);
ans.push_back(vector<int>());
return ans;
}
};
class Solution {
public:
void helper2(vector<int> &S, int k, int current, vector<int> &tmp, vector<vector<int>> &ans) {
if (k == 0) {
ans.push_back(tmp);
return;
}
for(int i = current; i <= S.size()-k; i++) {
tmp.push_back(S[i]);
helper2(S, k-1, i + 1, tmp, ans);
tmp.pop_back();
}
}
void findSubsetsWithLen(vector<int> &S, int k, vector<vector<int>> &ans) {
vector<int> tmp;
helper2(S, k, 0, tmp, ans);
}
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
vector<vector<int>> subsets(vector<int> &S) {
vector<vector<int>> ans;
sort(S.begin(), S.end());
for(int i = 0; i <= S.size(); i++) {
findSubsetsWithLen(S, i, ans);
}
return ans;
}
};
No comments:
Post a Comment