题解
Medium | Backtracking
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> sols;
vector<int> sol;
for(int i = 0; i <= nums.size(); i++) {
helper(nums, 0, i, sol, sols);
}
return sols;
}
void helper(vector<int>& nums, int pos, int k, vector<int>& sol, vector<vector<int>>& sols) {
if(k == sol.size()) {
sols.push_back(sol);
return;
}
for(int i = pos; i < nums.size(); i++) {
sol.push_back(nums[i]);
helper(nums, i+1, k, sol, sols);
sol.pop_back();
}
}
};
其实过程有一点冗余,可以简化为:
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> sols;
vector<int> sol;
helper(nums, 0, sol, sols);
return sols;
}
void helper(vector<int>& nums, int pos, vector<int>& sol, vector<vector<int>>& sols) {
sols.push_back(sol);
for(int i = pos; i < nums.size(); i++) {
sol.push_back(nums[i]);
helper(nums, i+1, sol, sols);
sol.pop_back();
}
}
};