Find all combinations that add upto given number

Given a positive number, find out all combinations of positive numbers that adds upto that number. The program should print only combinations, not permutations. For example, for input 3, either 1, 2 or 2, 1 should be printed.

For example,

Input: N = 3
Output:
1 1 1
1 2
3

Input: N = 5
Output:
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

We strongly recommend you to minimize your browser and try this yourself first.

The idea is to use recursion. We use an array to store combinations and we recursively fill the array and recurse with reduced number. The invariant used in the solution is that each combination will always be stored in increasing order of elements involved. That way we can avoid printing permutations.

Below is C++ implementation of above idea :

// C++ program to find out all combinations of
// positive numbers that add upto given number
#include <iostream>
using namespace std;
/*    arr - array to store the combination
    index - next location in array
    num - given number
    reducedNum - reduced number */
void findCombinationsUtil(int arr[], int index,
                       int num, int reducedNum)
{
    // Base condition
    if (reducedNum < 0)
        return;
    // If combination is found, print it
    if (reducedNum == 0)
    {
        for (int i = 0; i < index; i++)
            cout << arr[i] << " ";
        cout << endl;
        return;
    }
    // Find the previous number stored in arr[]
    // It helps in maintaining increasing order
    int prev = (index == 0)? 1 : arr[index-1];
    // note loop starts from previous number
    // i.e. at array location index - 1
    for (int k = prev; k <= num ; k++)
    {
        // next element of array is k
        arr[index] = k;
        // call recursively with reduced number
        findCombinationsUtil(arr, index + 1, num,
                                 reducedNum - k);
    }
}
/* Function to find out all combinations of
   positive numbers that add upto given number.
   It uses findCombinationsUtil() */
void findCombinations(int n)
{
    // array to store the combinations
    // It can contain max n elements
    int arr[n];
    //find all combinations
    findCombinationsUtil(arr, 0, n, n);
}
// Driver code
int main()
{
    int n = 5;
    findCombinations(n);
    return 0;
}

Output:

1 1 1 1 1 
1 1 1 2 
1 1 3 
1 2 2 
1 4 
2 3 
5 

Exercise: Modify above solution to consider only distinct elements in a combination.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/find-all-combinations-that-adds-upto-given-number-2/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar