WAP to Program The Combinations of Number That Sums Up to Given Traget Number..Print Unique Combinations Only

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)


Solution:
To search for all combination, we use a backtracking algorithm. Here, we use the above example of candidate={2,3,6,7} and target=7.

First, we start with a sum of 0. Then, we iterate over all possibilities that can be added to sum, which yields the possible set of sum={2,3,6,7}. Assume now that sum=2, we continue adding all possible candidate numbers {2,3,6,7} to sum=2, which yields sum={4,5,8,9}. Each step we have to use an array to keep track of all the indices of candidate numbers that add to the current sum, so that we can print the combination later. The next case would be sum=3. We look at all possible candidate numbers {3,6,7} to be added to sum=3, which yields sum={6,9,10}. Note that there is no need to look backward (ie, candidate numbers that are smaller than 3), as this would only yield duplicate results. We keep doing this recursively, until we reach the conditions below, where we stop.

We stop when the sum is greater than the target sum. Why? Remember our earlier assumption that candidate numbers must all be positive? Since the candidate array contains only positive numbers, if we continue searching, we would only add larger numbers to the sum, and this would not help us achieving the target sum. The other case where we stop is when the sum is equal to the target sum. We have found a valid combination.


#include
using namespace std;

void printSum(int candidates[], int index[], int n) {
for (int i = 1; i <= n; i++)
cout << candidates[index[i]] << ((i == n) ? "" : "+");
cout << endl;
}

void solves(int target, int sum, int candidates[], int sz, int index[], int n) {
if (sum > target)
return;
if (sum == target)
printSum(candidates, index, n);

for (int i = index[n]; i < sz; i++) {
index[n+1] = i;
solves(target, sum + candidates[i], candidates, sz, index, n+1);
}
}

void solve(int target, int candidates[], int sz) {
int index[10000];
index[0] = 0;
solves(target, 0, candidates, sz, index, 0);
}

int main()
{
int a[]={2,3,6,7};
solve(7,a,4);

}

I Discussed It with My Friend Ashim kapoor & after that we are able to solve4 it without repeatation

2nd Method

#define MAX_POINT 4
#define ARR_SIZE 100
#include

/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size);

/* The function prints all combinations of numbers 1, 2, ...MAX_POINT
that sum up to n.
i is used in recursion keep track of index in arr[] where next
element is to be added. Initital value of i must be passed as 0 */
void printCompositions(int arr[ARR_SIZE],int n, int i)
{

/* array must be static as we want to keep track
of values stored in arr[] using current calls of
printCompositions() in function call stack*/
// static int arr[ARR_SIZE];

if (n == 0)
{
printArray(arr, i);
}
else if(n > 0)
{
int k;
for (k = 1; k <= MAX_POINT; k++)
{
arr[i]= k;
printCompositions(arr,n-k, i+1);
}
}
}

/* UTILITY FUNCTIONS */
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size)
{
int i,flag=1;

for (i = 0; i < arr_size; i++)
if(arr[i]>arr[i+1]) flag=0;
if(flag)
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
}

/* Driver function to test above functions */
int main()
{
int n = 5;
printf("Differnt compositions formed by 1, 2 and 3 of %d are\n", n);
int arr[ARR_SIZE]={1,2,3,4};
printCompositions(arr,n, 0);
getchar();
return 0;
}

Run Here https://ideone.com/NCrkD


Java Code for doing the same.

class PrintAllCombi {



/**
* @param args
*/
public static void main(String[] args) {
int s = 6;
int[] a = new int[] {2,3,6,7,8};
getCombi(a, 0, s, 0, "");
}

private static void getCombi(int[] a, int j, int s, int currentSum, String st) {
if(s == currentSum) {
System.out.println(st);
return;
}
if(currentSum > s) {
return;
}
for(int i=j; igetCombi(a, i, s, currentSum+a[i], st+"+"+a[i]);
}
}


}

Run Here https://ideone.com/XiWAF