Be the first user to complete this post

Add to List 
Find all possible combinations with sum K from a given number N(1 to N) with the repetition of numbers is allowed
Objective: Given two integers N and K, Write an algorithm to find possible combinations that add to K, from the numbers 1 to N.
Condition: An integer from 1 to N can be repeated any number of times in combination.
Example:
N = 5 K = 3 Output: [1, 1, 1] [1, 2] [3] N = 6 K = 5 Output: [1, 1, 1, 1, 1] [1, 1, 1, 2] [1, 1, 3] [1, 2, 2] [1, 4] [2, 3] [5]
Approach: Use Recursion
 Given N and required sum K.
 Start with currSum = 0, startNumber = 0, combinationList=null
 Iterate through i = startNumber to N.
 Add i to currSum.
 Put i to combinationList.
 Make a recursive call with startNumber (to process next elements) and combinationList.
 In tail recursion, backtrack and remove i from the combinationList to find more solutions
 Base case: if currSum=K, Print combinationList.
Complete Code:
Output:
Given Number: 6, required sum K: 5 [1, 1, 1, 1, 1] [1, 1, 1, 2] [1, 1, 3] [1, 2, 2] [1, 4] [2, 3] [5]
Also Read: