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[index1];
// 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/findallcombinationsthataddsuptogivennumber2/
We have built the accelerating growthoriented 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