backtracking/dfs solution with intuition

• ``````/**
* intuition:
*
* [10, 1, 2, 7, 6, 1, 5], 8
*
* 1. sort the candidates
* [1, 1, 2, 5, 6, 7, 10], 8
*
* 2. total solution =
* t            new candidates new target
* 1 + solution([1,2,5,6,7,10], t - 1) +
* 1 + solution([2,5,6,7,10],   t - 1) +  // duplicate to previous one, remove
* it
* 2 + solution([5,6,7,10],     t - 2) +
* 5 + solution([6,7,10]),      t - 5) +
* ...
*
*/
class Solution {
public:
std::vector<std::vector<int>> mResult;
vector<vector<int>> combinationSum2(const vector<int>& candidates,
int target) {
auto candi(candidates);
std::sort(candi.begin(), candi.end());
std::vector<int> path;
dfs(candi, path, target);
return mResult;
}

void dfs(const vector<int>& candidates, vector<int>& path, int target) {
// log(candidates, path, target);
if (target == 0) {
mResult.push_back(path);
return;
} else if (target < 0) {
return;
}
auto candi(candidates);
while (!candi.empty()) {
int t = candi[0];
path.push_back(t);
// since each one can only be used once, we should remove it
candi.erase(candi.begin());
// dfs with new candidates and new target
dfs(candi, path, target - t);
// backtracking
path.pop_back();
// remove all element that is duplicate to t, see comments in intuition
// move to next possible sub solution
candi.erase(std::remove(candi.begin(), candi.end(), t), candi.end());
}
}
}
``````

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