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 combinationSumHelper(vector<vector<int>>& result,
02      vector<int> &candidates, vector<int>& current, int pos, int remain)
03 {
04     if(remain==0)
05     {
06         result.push_back(current);
07         return;
08     }
09     int n=candidates.size();
10     if((pos>=n)||(candidates[pos]>remain))
11         return;
12     current.push_back(candidates[pos]);
13     combinationSumHelper(result,candidates,current,
14                          pos,remaincandidates[pos]);
15     current.pop_back();
16     combinationSumHelper(result,candidates,
17                          current,pos+1,remain);
18 }
19 bool myfunction (int i,int j) { return (i<j); }
20 class Solution {
21 public:
22     vector<vector<int> > combinationSum(vector<int>
23                                         &candidates, int target) {
24         // Start typing your C/C++ solution below
25         // DO NOT write int main() function
26         vector<vector<int>> result;
27         vector<int> current;
28         sort(candidates.begin(),candidates.end(),myfunction);
29         combinationSumHelper(result,candidates,current,0,target);
30         return result;
31     }
32 };
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