# C++ backtracking solution with detailed explanation

• At the beginning, I stuck on this problem. After careful thought, I think this kind of backtracking contains a iterative component and a resursive component so I'd like to give more details to help beginners save time. The revursive component tries the elements after the current one and also tries duplicate elements. So we can get correct answer for cases like [1 1] 2. The iterative component checks duplicate combinations and skip it if it is. So we can get correct answer for cases like [1 1 1] 2.

``````class Solution {
public:
vector<vector<int> > combinationSum2(vector<int> &num, int target)
{
vector<vector<int>> res;
sort(num.begin(),num.end());
vector<int> local;
findCombination(res, 0, target, local, num);
return res;
}
void findCombination(vector<vector<int>>& res, const int order, const int target, vector<int>& local, const vector<int>& num)
{
if(target==0)
{
res.push_back(local);
return;
}
else
{
for(int i = order;i<num.size();i++) // iterative component
{
if(num[i]>target) return;
if(i&&num[i]==num[i-1]&&i>order) continue; // check duplicate combination
local.push_back(num[i]),
findCombination(res,i+1,target-num[i],local,num); // recursive componenet
local.pop_back();
}
}
}
};``````

• for the following line:
if(i&&num[i]==num[i-1]&&i>order) continue; // check duplicate combination.
I think you can also write in other words:
if(i == order || num[i-1] != num[i]){local.push_back(num[i]); findCombination(res,i+1,target-num[i],local,num); local.pop_back();} // with the following 3 lines inside the parenthesis

• Thanks a lot!

• if there is 1 1 1 2， and how can you get only one [1 ,1] result? could you plz explain?

• You don't need else block

• @yanchao_hust

if(i&&num[i]==num[i-1]&&i>order) continue; // check duplicate combination

this code will help to skip the duplicate.
BTW,the first condition is unnecessary.Just swap the position of the second condition and the third conditio.

• What is the time complexity and space of this code?

• Another way:

``````vector<vector<int>> combinationSum2(vector<int>& A, int target) {
vector<vector<int>> res;
vector<int> path;
sort(A.begin(), A.end());
combinationSum2(A, 0, path, target, res);
return res;
}

void combinationSum2(vector<int>& A, int pos, vector<int> &path, int target, vector<vector<int>> &res) {
if (target == 0) {
res.push_back(path);
return;
}
if (pos == A.size() || target - A[pos] < 0) return;
auto num = A[pos++];
path.push_back(num);
combinationSum2(A, pos, path, target - num, res);
path.pop_back();

while (A[pos] == num) ++pos;
combinationSum2(A, pos, path, target, res);
}
``````

• @yanchao_hust because the array is sorted at the very beginning.

• ``````if(i&&num[i]==num[i-1]&&i>order) continue; // check duplicate combination
``````

I kind of get it but can someone explain how does this work to prevent duplicates?
If `i` is the same as `order`, then `nums[i]` is being included for the first time as a candidate.
But if `i > order`, then `nums[i]` is starting over using a duplicate number. Is this correct?

• @wfxr I think this is clearer.

• ``````  vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> res;
vector<vector<int>> allres;

sort(candidates.begin(),candidates.end());
combination(res,allres,0,target,candidates);
return allres;
}
void combination(vector<int> &res,vector<vector<int>> &allres,int begin,int target,vector<int>& candidates) {
if(target==0){
allres.push_back(res);
return;
}
for(int i=begin;i<candidates.size()&&candidates[i]<target;i++) {
if(i&&candidates[i]==candidates[i-1]&&i>begin) continue;
res.push_back(candidates[i]);
combination(res,allres,i+1,target-candidates[i],candidates);
res.pop_back();
}
}
``````

why is it wrong? the result of run is null;

• My solution with different way to deal with the duplicate combination.
Explain it with the example ：

[1,1,2,5,6,7,10] and k = 7

Here is a map to record the times of one element appears. For example，m[1] =2, m[2]=1, etc。

For element 1, we can choose one or two. Then the sub question is like this:

1. Choose 1 time, then find target = 7 - 1*1 in subarray [2,5,6,7,10]
2. Choose 2 times, then find target = 7 - 1*2 in subarray [2,5,6,7,10]
``````
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
{
vector<vector<int>> ans;
vector<int> v;
sort(candidates.begin(), candidates.end());

for (auto i:candidates)
m[i]++;

combinationSum2(ans, v, target, candidates, 0);
return ans;
}

void combinationSum2(vector<vector<int>> &ans, vector<int> &v, int target, vector<int> candidates, int begin)
{
if (!target)
{
ans.push_back(v);
return;
}
for (int i = begin; i < candidates.size() && target >= candidates[i]; i += m[candidates[i]])
{
for (int k = 1; k <= m[candidates[i]]; ++k)
{
for (int j = 1; j <= k; ++j)
{
v.push_back(candidates[i]);
}

combinationSum2(ans, v, target - candidates[i] * k, candidates, i + m[candidates[i]]);

for (int j = 1; j <= k; ++j)
{
v.pop_back();
}

}
}
}

map<int, int> m;
};
``````

• @chaopengz could you please explain the duplicate problem? I am unable to recognize the problem in the first place let alone solve it

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