Problem

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

Analysis

We can use DFS to recursive build the solution, i.e.,
let sol denote current solution,
let allSol denote all solutions,
let remain denote current remaining value to reach target in sol,
let start denote current traversing index in vector candidates
– we need to define terminate condition of DFS (i.e., when remain == 0)
– decide how/when to recursive build sol

Time complexity: O(2^n)
Space complexity: O(d) where d is the depth

Solution

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> allSol; 
        if(candidates.empty()) return allSol;
        
        vector<int> sol;
        int remain = target;
        int start = 0;
        sort(candidates.begin(), candidates.end());
        findComb(allSol, sol, start, remain, candidates);
        return allSol;
    }
    
    //DFS
    void findComb(vector<vector<int>>& allSol, vector<int>& sol, int start, int remain, vector<int>& candidates){
        //check terminate state
        if(remain == 0){
            allSol.push_back(sol);
            return;
        }
        
        //recursive construct solution
        for(int i=start; i<candidates.size(); i++){
            if(i>start && candidates[i-1] == candidates[i]) continue;
            if(candidates[i] <= remain){
                //push back
                sol.push_back(candidates[i]);
                findComb(allSol, sol, i, remain - candidates[i], candidates);
                //pop back
                sol.pop_back();
            }else{
                break;
            }
        }
    }
};