39 Combination Sum

Given a set of candidate numbers (C) 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]
]

Solution:

class Solution {
public:
    int sum(vector<int>& nums) {
        int res = 0, n = nums.size();
        if ( n == 0 ) return res;
        for ( int i = 0; i <= n-1; i++ ) res += nums[i];
        return res;
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int n = candidates.size();
        vector<vector<int>> res;
        vector<vector<int>> tmp_res1;
        vector<int> tmp;
        tmp_res1.push_back(tmp);
        for ( int i = 0; i <= n-1; i++ ) {
            int nres = tmp_res1.size();
            for ( int j = 0; j <= nres-1; j++ ) {
                tmp = tmp_res1[j];
                int s = sum(tmp_res1[j]);
                int icount = (target-s)/candidates[i];
                for ( int k = 1; k <= icount; k++) {
                    tmp.push_back(candidates[i]);
                    if ( s + candidates[i]*k == target ) res.push_back(tmp);
                    else tmp_res1.push_back(tmp);
                }
            }
        }
        return res;
    }
};

Recursive Solution

class Solution {
public:
    void help(vector<int>& candidates, int i0, vector<int> curr, int target, vector<vector<int>>& res) {
        if ( target == 0 ) {res.push_back(curr); return;}
        int n = candidates.size();
        if ( i0 == n ) return;
        while ( target >= 0 ) {
            help(candidates, i0+1, curr, target, res);
            curr.push_back(candidates[i0]);
            target -= candidates[i0];
        }
        return;
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> curr;
        help(candidates, 0, curr, target, res);
        return res;
    }
};