Combination Sum

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.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• 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] 

------------------------ thinking --------------------------------------

Please read the requirement very carefully! here we can see we can duplicate the input data as many as possible, so when input is [1] and target is 2, we can get the result [1, 1]

So my first codes don't work at all. Please comparing the right codes and wrong codes, to see the difference.

-------------------------------------------- wrong codes -----------------------------
class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int>> result;
        vector<int> curSol;
        sort(candidates.begin(), candidates.end());
        combSum(candidates, 0, curSol, target, result);
        return result;
    }
    void combSum(vector<int>& candidates, int next, vector<int> &curSol, int target, vector<vector<int>> &result) {
        if (target == 0) {
            result.push_back(curSol);
        }
        if (next == candidates.size() || candidates[next] > target) {
            return;
        }

        //here the assumption is each input element can only be used for one time
        //please compare the difference between the rest codes with right codes
        curSol.push_back(candidates[next]);
        combSum(candidates, next + 1, curSol, target - candidates[next], result);
        curSol.pop_back();
        
        int i = next + 1;
        while (i < candidates.size() && candidates[i] == candidates[next]) {
            i++;
        }
        combSum(candidates, i, curSol, target, result);

    }

};

------------------------------------ right codes ------------------------------------------------
class Solution {
    void help(vector<int>& now, vector<int>&candidates, int index, int target, vector<vector<int>>& results)
    {
        for(int i = index;i < candidates.size();i++)
        {
            if(candidates[i] < target)
            {
                now.push_back(candidates[i]);
                help(now, candidates, i, target-candidates[i], results);
                now.pop_back();
            } else if(candidates[i] == target) {
                now.push_back(candidates[i]);
                results.push_back(now);
                now.pop_back();
            }
        }
    }

public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int>> results;
        vector<int>tmp;
        sort(candidates.begin(), candidates.end());
        help(tmp, candidates, 0, target, results);
        return results;
    }

};