Combination Sum II

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

Each number in C may only be used once in the combination.

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 10,1,2,7,6,1,5 and target 8
A solution set is: 
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6] 

C++:
01 void cSum(const int A[], int size, int target, int index, vector<vector<int> >& v, vector<int> cur)
02 {
03      if(target==0){
04          v.push_back(cur);
05          return;
06      }
07      if((index>=size)||(target<0))
08          return;
09      int data=A[index];
10      int tmp=index;
11      do{tmp++;}while((tmp<size)&&(A[tmp]==A[tmp1]));
12      cSum(A,size,target,tmp, v, cur);
13      cur.push_back(data);
14      cSum(A,size,targetdata,index+1,v,cur);
15 }
16 
17  vector<vector<int> > combinationSum2(vector<int> &num, int target) {
18        vector<vector<int> > result;
19        vector<int> cur;
20        int n=num.size();
21        int* A=new int[n];
22        for(int i=0;i<n;i++)
23            A[i]=num[i];
24        qsort(A,n,sizeof(int),compare);
25        cSum(A,n, 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