Leetcode 上的组合和 III

Question

leetcode题目是：

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.

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]]

我在 Javascript

中找到了解决方案

var combinationSum3 = function(k, n) {
  var result = [];
  search(1, [], k, n);
  return result;

  function search(from, prefix, k, n) {
    if (k === 0 && n === 0) return result.push(prefix);
    if (from > 9) return;
    prefix.push(from);
    search(from + 1, prefix.slice(0), k - 1, n - from);
    prefix.pop();
    search(from + 1, prefix.slice(0), k, n);
  }
};

我假设 slice(0) 方法 return 是原始数组的副本，所以我尝试用前缀替换 prefix.slice(0)。但是，我得到的结果是 [ [ ] ]。这里的问题是什么？

Answer 1

引用有问题。如果你使用 slice，你会得到一个数组的副本。如果您只使用 prefix，那么所有后续操作，如 push 或 pop 都会影响数组。

如果您不喜欢使用副本，您可以使用 concat，它也提供一个新数组，但使用新的 item/s.

您的代码如下所示：

var combinationSum3 = function (k, n) {
    var result = [];
    search(1, [], k, n);
    return result;

    function search(from, prefix, k, n) {
        if (k === 0 && n === 0) return result.push(prefix);
        if (from > 9) return;
        search(from + 1, prefix.concat(from), k - 1, n - from);
        search(from + 1, prefix, k, n);
    }
};

console.log(combinationSum3(3, 7));
console.log(combinationSum3(3, 9));
console.log(combinationSum3(4, 12));

Leetcode 上的组合和 III

Combination Sum III on Leetcode

javascript

arrays

algorithm

slice