Print all combinations of a number as a sum of candidate numbers

Given a target number, and a series of candidate numbers, print out all combinations, so that the sum of candidate numbers equals to the target. 

Here order is not important, so don’t print the duplicated combination.

e.g. target is 7, candidate is 2,3,6,7
output should be 7 and 3+2+2 (but not print 2+3+2, 2+2+3)

Please note that the same repeated number may be chosen from the candidate set. We may also assume that the candidate set does not contain duplicate numbers, as this will be redundant. We assume all numbers will be positive integers, I will explain why this assumption is important for obtaining a solution later.

Hint:
Think about how to avoid printing duplicates. Think about developing a systematic method to search all possible solutions. How do you determine the condition that ends the search? 

C++:
01 void Print_sum(int A[],int size,int start, int B[], int target)
02 {
03     if((target<0)||(start>=size))
04         return;
05     int flag=0;
06     int *C=new int[size];
07     for(int i=0;i<size;i++)
08         C[i]=B[i];
09     if(target==0)
10     {
11         for(int i=0;i<size;i++){
12             while(C[i]>0){
13                 if(flag==0){
14                     flag=1;
15                     cout<<A[i];
16                 }
17                 else{
18                     cout<<“+”<<A[i];
19                 }
20                 C[i];
21             }
22         }
23         cout<<endl;
24     }
25     else{
26         Print_sum(A,size,start+1,C,target);
27         C[start]++;
28         Print_sum(A,size,start,C,targetA[start]);
29     }
30 }
Advertisements
This entry was posted in Array and linked list, Backtrack, Number trick. 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