class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> sol;
vector<int> state;
sort(candidates.begin(), candidates.end());
backtrack(candidates, target, state, sol, 0);
return sol;
}
private:
void backtrack(vector<int>& candidates, int target, vector<int>& state, vector<vector<int>>& sol, int begin) {
if(target == 0)
sol.push_back(state);
else if (target < 0)
return;
else
{
for(int i=begin; i<candidates.size(); i++)
{
state.push_back(candidates[i]);
backtrack(candidates, target-candidates[i], state, sol, i);
state.pop_back();
}
}
}
};