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

  1. Given N and required sum K.
  2. Start with currSum = 0, startNumber = 0, combinationList=null
  3. Iterate through i = startNumber to N.
    1. Add i to currSum
    2. Put i to combinationList.
    3. Make a recursive call with startNumber (to process next elements) and combinationList.
    4. In tail recursion, backtrack and remove i from the combinationList to find more solutions 
    5. 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]

__________________________________________________
Top Companies Interview Questions..-

GoogleMicrosoftAmazonFacebookmore..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

Leave a Reply

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

%d bloggers like this: