# A simple solution using backtracking without using a set to handle duplicates

• ``````class Solution {
public:
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
sort(num.begin(), num.end());

vector<vector<int>> res;
vector<int> cur;
int cur_sum = 0;
backtrack(num, target, 0, res, cur, cur_sum);

return res;
}

void backtrack(const vector<int> &num, int target, int low,
vector<vector<int>> &res, vector<int> &cur, int &cur_sum)
{
if (cur_sum == target)
{
res.push_back(cur);
return;
}

if (cur_sum > target)
return;

for (int i = low; i < num.size(); ++i)
{
cur_sum += num[i];
cur.push_back(num[i]);

backtrack(num, target, i + 1, res, cur, cur_sum);

cur.pop_back();
cur_sum -= num[i];

//handling duplicates:
//simply don't start any new combinations with a duplicate
while (i < num.size() - 1 && num[i + 1] == num[i])
++i;
}
}
};``````

• Your solution is a good example of backtracking! Thanks!

• Thanks for handling duplicates part

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