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 (a1a2, … ,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] 

C++:
01 void cSum(const vector<int> &set, int target, int index, vector<vector<int> >& v, vector<int> cur)
02 {
03      if((index>=set.size())||(target<0))
04          return;
05      if(target==0){
06          v.push_back(cur);
07          return;
08      }
09      cSum(set,target,index+1, v, cur);
10      cur.push_back(set[index]);
11      cSum(set,targetset[index],index,v,cur);
12 }
13 
14 vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
15        vector<vector<int> > result;
16        vector<int> cur;
17        int n=candidates.size();
18        int *A=new int[n];
19        for(int i=0;i<n;i++)
20            A[i]=candidates[i];
21        qsort(A,n,sizeof(int),compare);
22        vector<int> scand;
23        for(int i=0;i<n;i++)
24        scand.push_back(A[i]);
25        cSum(scand,target,0,result,cur);
26        return result;
27 }
Advertisements
This entry was posted in Array and linked list, Dynamic programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s