# 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
and required sum*N*.*K* - Start with
= 0,*currSum*= 0,*startNumber*=null*combinationList* - Iterate through
=*i*to*startNumber*.*N*- Add
to*i*.*currSum* - Put
to*i**combinationList.* - Make a recursive call with
(to process next elements) and*startNumber**combinationList.* - In tail recursion, backtrack and remove
from the*i*to find more solutions*combinationList* - Base case: if
*currSum=K*.*combinationList*

- Add

**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]