# 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

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

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

__________________________________________________
Top Companies Interview Questions..-

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