Combination Sum I

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 <code>2,3,6,7</code> and target <code>7</code>, 

A solution set is: 

<code>[7]</code> 

<code>[2, 2, 3]</code> 

解法：

由題意為set知，集合應該沒有重複元素；用回溯法。

注意，每個元素可以取多次，

void  combinationCore(vector&lt;int&gt; &amp;candi,int target,int begin,vector&lt;int&gt; &amp;tempresult,vector&lt;vector&lt;int&gt; &gt; &amp;results){

        if(target==0){//target==0,說明已經找到一個可行解

            results.push_back(tempresult);

        }

        else{

            int size=candi.size();

            for(int i=begin;i&lt;size&amp;&amp;target&gt;=candi[i];++i){

         //target&gt;=candi[i],因為同一個元素可以取多次，則i從begin開始，且下一個也是從i開始，

                tempresult.push_back(candi[i]);

                combinationCore(candi,target-candi[i],i,tempresult,results);

                tempresult.pop_back();

            }

    }

    vector&lt;vector&lt;int&gt;&gt; combinationSum(vector&lt;int&gt;&amp; candidates, int target) {

        vector&lt;vector&lt;int&gt;&gt; results;

        int size=candidates.size();

        if(size==0||target&lt;=0)

            return results;

        vector&lt;int&gt; temp;

        sort(candidates.begin(),candidates.end());//must

        combinationCore(candidates,target,0,temp,results);

        return results;