Combination Sum III

Description

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

• All numbers will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

Solution(javascript)

// /** 1.1: Backtracking
//  * @param {number} k
//  * @param {number} n
//  * @return {number[][]}
//  */
// const combinationSum3 = function (k, n) {
//   const result = []
//   const aux = (start, current, sum) => {
//     if (current.length > k) {
//       return
//     }
//     if (current.length === k) {
//       if (sum === n) {
//         result.push(current)
//         return
//       }
//       return
//     }

//     for (let i = start; i <= 9; i++) {
//       aux(i + 1, [...current, i], sum + i)
//     }
//   }
//   for (let i = 1; i <= 9; i++) {
//     aux(i + 1, [i], i)
//   }
//   return result
// }


/** 1.2: Backtracking
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
const combinationSum3 = function (k, n) {
  const result = []
  const aux = (start, current, sum) => {
    if (current.length > k) {
      return
    }
    if (current.length === k) {
      if (sum === n) {
        result.push([...current])
        return
      }
      return
    }

    for (let i = start; i <= 9; i++) {
      current.push(i)
      aux(i + 1, current, sum + i)
      current.pop(i)
    }
  }
  for (let i = 1; i <= 9; i++) {
    aux(i + 1, [i], i)
  }
  return result
}