Question:

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
  2. Output: [[1,2,4]]
  1. Input: k = 3, n = 9
  2. Output: [[1,2,6], [1,3,5], [2,3,4]]

Solution:

  1. /**
  2.  * @param {number} k
  3.  * @param {number} n
  4.  * @return {number[][]}
  5.  */
  6. var combinationSum3 = function(k, n) {
  7.   const result = [];
  8.   let dfs = function (num, path, fromNum) {
  9.     if (num === 0 && path.length === k) {
  10.       result.push(path);
  11.     }
  12.     if (path.length < k) {
  13.       for ( let i = fromNum; i < 10; i++) {
  14.         let nextPath = Object.assign([],path);
  15.         nextPath.push(i);
  16.         dfs(num-i,nextPath,i+1);
  17.       }
  18.     }
  19.   }
  20.   //递归调用
  21.   dfs(n,[],1);
  22.   return result;
  23. };

Runtime: 56 ms, faster than 55.65% of JavaScript online submissions for Combination Sum III.