This post is completed by 1 user

  • 0
 Add to List
Medium

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

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]

Related Problems: