# Accepted 10ms c++ solution use backtracking, only 10 lines, easy understand.

• The characteristics of C++ reference is an outstanding tool for backtracking algorithm!

let us use [1,2,3,4] as an example to explain my solution:

``````subsets([1,2,3,4]) = []
// push(1)
[1, subsets([2,3,4])] // if push N times in subsets([2,3,4]), the pop times is also N, so vec is also [1] after backtrack.
// pop(), push(2)
[2, subsets([3,4])]
// pop(), push(3)
[3, subsets([4])]
// pop(), push(4)
[4, subsets([])]
// pop()
``````

Accepted 10ms c++ solution use backtracking for Subsets

``````class Solution {
public:
std::vector<std::vector<int> > subsets(std::vector<int> &nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int> > res;
std::vector<int> vec;
subsets(res, nums, vec, 0);
return res;
}
private:
void subsets(std::vector<std::vector<int> > &res, std::vector<int> &nums, std::vector<int> &vec, int begin) {
res.push_back(vec);
for (int i = begin; i != nums.size(); ++i) {
vec.push_back(nums[i]);
subsets(res, nums, vec, i + 1);
vec.pop_back();
}
}
};
``````

Accepted 10ms c++ solution use backtracking for Subsets II

``````class Solution {
public:
std::vector<std::vector<int> > subsetsWithDup(std::vector<int> &nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int> > res;
std::vector<int> vec;
subsetsWithDup(res, nums, vec, 0);
return res;
}
private:
void subsetsWithDup(std::vector<std::vector<int> > &res, std::vector<int> &nums, std::vector<int> &vec, int begin) {
res.push_back(vec);
for (int i = begin; i != nums.size(); ++i)
if (i == begin || nums[i] != nums[i - 1]) {
vec.push_back(nums[i]);
subsetsWithDup(res, nums, vec, i + 1);
vec.pop_back();
}
}
};
``````

• Good explanation, and share my iterative method:

`````` vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> ret;
ret.push_back(vector<int>());
sort(nums.begin(), nums.end());
vector<vector<int>> sub;
for (int i = 0; i < nums.size(); ++i) {
if (i == 0 || nums[i] != nums[i-1]) sub = ret;
for (auto& j:sub) j.push_back(nums[i]);
ret.insert(ret.end(), sub.begin(), sub.end());
}
return ret;
}``````

• I love your solution, though mine is a little different.

``````void subsetsWithDup(vector<int>& nums, vector<int> res, vector<vector<int>>& ans, int start) {
if (start == nums.size()) {
ans.push_back(res);
return;
}
subsetsWithDup(nums,res,ans,start+1);
while (start + 1 < nums.size() && nums[start] == nums[start+1]) {
res.push_back(nums[start]);
++start;
}
res.push_back(nums[start]);
subsetsWithDup(nums,res,ans,start+1);
}

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<int> res;
vector<vector<int>> ans;
sort(nums.begin(),nums.end());
subsetsWithDup(nums,res,ans,0);
return ans;
}``````

• what's the time complexity of your code ?

• I think it is O(2^n), you can calculate the total push times as follow:

``````t(0) = 0
t(1) = 1+t(0)
t(2) = 2+t(1)+t(0)
...
t(n-1) = n-1+t(n-2)+t(n-3)+...+t(1)+t(0)
t(n) = n+t(n-1)+t(n-2)+...+t(1)+t(0) = n+t(n-1)+t(n-1)-n+1=2t(n-1)+1

=> t(n)+1 = 2(t(n-1)+1) => t(n)+1 = 2^n => t(n) = 2^n-1``````

• Upvoted. This is the solution I am looking for, which is consistent with the approach -- "for each index, pick, or not".

• My first solution for subset I & II is a little different but also straightforward:

1. `subsetsWithDup([A, B]) = SubsetsWithDup(subsetsWithDup([A]), subsetsWithDup([B]))`
2. `subsetsWithDup([A])` where `A` contains same number `[A]=[a,a,...]`, is easy to find the solution:`[],[a],[a,a],[a,a,a]...`
``````class Solution {
private:
void subsetAux(vector<int> & nums, vector<vector<int>>& res, vector<int>& subset, int begin) {
if(begin==nums.size()) {
res.push_back(subset);
return;
}
int numSam = 1;
while(begin+numSam<nums.size()&&nums[begin+numSam]==nums[begin]) numSam++;
for(int i=0;i<=numSam;i++) {
for(int j=0;j<i;j++) {
subset.push_back(nums[begin]);
}
subsetAux(nums, res, subset, begin+numSam);
for(int j=0;j<i;j++) {
subset.pop_back();
}
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> res;
vector<int> subset;
subsetAux(nums, res, subset, 0);
return res;
}
};
``````

• @Ervine i m beginner in c++. I am trying to understand since ur function is a recursive function, where is the return in it ?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.