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

- Given
.*N* - Start with
= 0,*sum*= 0,*start*=null*combinationList* - Iterate through
=*i*to*start*.*9*- Add
to*i*.*sum* - Put
to*i**combinationList.* - Make a recursive call with
(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
*sum=N*.*combinationList*

- Add

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