Find number of combinations possible in array that sum up to given number
Answers
Answered by
1
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.
Examples :
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.
Similar questions
Hindi,
5 months ago
English,
5 months ago
Math,
11 months ago
Social Sciences,
11 months ago
Social Sciences,
1 year ago