Friday, September 2, 2011

Given an array and a sum S output all combination of elements that sum to S

Example: 1 2 3

sum = 3
1+1+1,
2+1
3

Program:

int arr[] = {1,2,3};
void printcombination(int n, int index, int i)
{
  static int a[100];
  int j;
  // sum is equal to zero print all numbers that form the sum. 
  if(n == 0)
  {
     for(j =0;j 0)
  {
    for(j = i; j < 3;j++)
    {
       a[index] = arr[j];
       // call printcombination only when the difference is greater than or equal to zero
       if(n-arr[j] >= 0)
          printcombination(n-arr[j], index + 1, j);
    }
  }
 
}

main()
{
  int sum = 3;
  printcombination(sum, 0, 0);
  return 0;  
}

No comments:

Post a Comment