// https://leetcode.com/problems/subsets/
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<int>::const_iterator it = nums.cbegin();
vector<int>::const_iterator end = nums.cend();
return *(subsets(it, end));
}
private:
vector<vector<int>>* subsets(vector<int>::const_iterator it, vector<int>::const_iterator end) {
vector<vector<int>>* result = new vector<vector<int>>();
// Base case
if (it == end) {
vector<int>* emptyVec = new vector<int>();
result->emplace_back(*emptyVec);
return result;
}
int curVal = *(it++);
vector<vector<int>>* subProblemResult = subsets(it, end);
auto subProblemIt = subProblemResult->begin();
int subProblemResultSize = subProblemResult->size();
for (int i = 0; i < subProblemResultSize; i++) {
vector<int>* curSet = new vector<int>(*subProblemIt);
curSet->emplace_back(curVal);
subProblemResult->emplace_back(*curSet);
++subProblemIt;
}
return subProblemResult;
}
};