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.
  2. Start with sum = 0, start = 0, combinationList=null
  3. Iterate through i = start to 9.
    • Add i to sum
    • 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]

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: