array_elements_whose_sum_is_equal_to_a_given_number_v2.c

/*

    array_elements_whose_sum_is_equal_to_a_given_number_v2.c

https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/

There is given an array arr[] of n integers.
Write program in C to find all combinations of array elements
whose sum is equal to a given number sum.


    You can find all my C programs at Dragan Milicev's pastebin:

    https://pastebin.com/u/dmilicev

*/

#include <stdio.h>
#include <stdlib.h>

// Prints an array a[] of length n
void print_array(int a[], int n){
    for (int i=0; i<n; i++)
        printf("%3d", a[i]);
    printf("\n");
}

/*
arr[]       ---> Input Array
data[]      ---> Temporary array to store current combination
start & end ---> Starting and Ending indexes in arr[]
index       ---> Current index in data[]
k           ---> Size of a combination to be printed
*/
void combinationUtil(int arr[], int data[], int start, int end,
                        int index, int k, int sum)
{
    int s = 0;                  // the sum of the current combination

    // Current combination is ready to be printed, print it
    if (index == k)             // if the combination is complete, finished
    {
        for (int j=0; j<k; j++) // calculate sum s for that combination
            s += data[j];

        if(s==sum){             // print sum s for that combination
            for (int j=0; j<k; j++)
                printf("%d ", data[j]);
            printf("\n");
        }
        return;                 // exit from recursive function
    }

    // replace index with all possible elements. The condition
    // "end-i+1 >= k-index" makes sure that including one element
    // at index will make a combination with remaining elements
    // at remaining positions
    for (int i=start; i<=end && end-i+1 >= k-index; i++)
    {
        data[index] = arr[i];
        combinationUtil(arr, data, i+1, end, index+1, k, sum);
    }
} // combinationUtil()

// The main function that prints all combinations of size k
// in arr[] of size n. This function mainly uses combinationUtil()
void printCombinationWithSum(int arr[], int n, int k, int sum) {
    // A temporary array to store all combination one by one
    int data[k];

    // Print all combination using temporary array data[]
    combinationUtil(arr, data, 0, n-1, 0, k, sum);
}


// Program to print all combination of size k in an array of size n
int main(){
    int arr[] = {1,2,3,4,5,6,7,8,9};        // array of n integers
    int n = sizeof(arr)/sizeof(arr[0]);     // count the number of array members
    int sum = 10;                           // the required sum of the elements of the array

    printf("\n Elements are: \n\n");

    print_array(arr,n);

    printf("\n All combinations of array elements whose sum is equal to %d are: \n\n",sum);

    for (int i=1; i<=n; i++)                // for all combinations whose length is from 1 to n
        printCombinationWithSum(arr, n, i, sum);

} // main()