This post is completed by 1 user

  • 0
 Add to List
Medium

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

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]

Related Problems: