# Find all unique combinations of exact K numbers (from 1 to 9 ) with sum to N

**Objective: **Given two integers N and K. Write an algorithm to find all the combinations of k numbers which sum to N.

**Conditions: **

- All K numbers must be between 1 and 9 and unique.
- All numbers in K are positive.

**Example:**

N= 5 K=2 Output: [1, 4] [2, 3] N =12 K=3 Output: [1, 2, 9] [1, 3, 8] [1, 4, 7] [1, 5, 6] [2, 3, 7] [2, 4, 6] [3, 4, 5]

**Approach: Use Recursion**

- Given
and*N*.*K* - Start with
= 0,*sum*= 1,*start*=null*combinationList* - Iterate through
=*i*to*start*.*9*- Add
to*i*.*sum* - Put
to*i**combinationList.* - Make a recursive call with
and*K-1*(to avoid duplicates) and*start = start + 1**combinationList.* - In tail recursion, backtrack and remove i from the
to find more solutions*combinationList* - Base case: If
, check if*K=0**sum=N*.*combinationList*

- Add

**Complete Code:**

**Output:**

N = 12 K = 3 [1, 2, 9] [1, 3, 8] [1, 4, 7] [1, 5, 6] [2, 3, 7] [2, 4, 6] [3, 4, 5]