class Solution {
public:
void subsetsHelper(vector<int>& nums, size_t pos, vector<int> & chosen, vector< vector<int> > & allsubsets){
// a helper function
// here a choice is w.r.t. a given position "pos" : should we include element at this position into our results?
if (pos == nums.size())
allsubsets.push_back(chosen); // no more choices to make
else{
// choose
// 1. include element at current position
chosen.push_back(nums[pos]);
subsetsHelper(nums, pos+1, chosen, allsubsets);
chosen.pop_back();
// 2. not include element at current position
subsetsHelper(nums, pos+1, chosen, allsubsets);
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> chosen = {};
vector< vector<int> > allsubsets = {};
subsetsHelper(nums, 0, chosen, allsubsets);
return allsubsets;
}
};
A backtracking problem : choose, explore, unchoose...
Mistake: Stopping condition.
- I used pos == nums.size()-1 but this will ignore the last element
- The stopping condition is when VIOLATING the condition so should be pos == nums.size().
Mistake: Stopping condition.
- I used pos == nums.size()-1 but this will ignore the last element
- The stopping condition is when VIOLATING the condition so should be pos == nums.size().
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.