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

Objective: Given an integer N, Write an algorithm to select numbers from 1 to 9 and make combinations such that its sum to N.

Example:

```N= 5
Output:
[1, 4]
[2, 3]
[5]

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

Approach: Use Recursion

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

Complete Code:

Output:

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

__________________________________________________
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.
__________________________________________________