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 bool Compare(int i, int j)
02 {
03     return i<j;
04 }
05 void combinationHelper(vector<vector<int>>& result,
06 vector<int> &num, int pos, int remain, vector<int>& current)
07 {
08     int n=num.size();
09     if(remain==0)
10     {
11         result.push_back(current);
12         return;
13     }
14     if(pos>=n)  return;
15     int item=num[pos];
16     if(item>remain) return;
17     current.push_back(item);
18     combinationHelper(result,num,pos+1,remainitem,current);
19     current.pop_back();
20     while((pos<n)&&(num[pos]==item)) pos++;
21     combinationHelper(result,num,pos,remain,current);
22 }
23 class Solution {
24 public:
25     vector<vector<int> > combinationSum2(vector<int> &num,
26     int target) {
27         // Start typing your C/C++ solution below
28         // DO NOT write int main() function
29         vector<vector<int>> result;
30         vector<int> current;
31         sort(num.begin(),num.end(),Compare);
32         combinationHelper(result,num,0,target,current);
33         return result;
34     }
35 };
Advertisements
This entry was posted in Array and linked list, Recursive. 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