组合问题 - 给定两个整数 n 和 k，编写一个程序 return 1 2 3 n 中 k 个数字的所有可能组合

Question

我正在尝试使用 JS 解决简单的算法：

给定两个数字 n 和 k，你必须从 1…n 中找到 k 个数字的所有可能组合。

Input : n = 5 
        k = 3

Output : 1 2 3 
         1 2 4 
         1 2 5 
         1 3 4 
         1 3 5 
         1 4 5 
         2 3 4 
         2 3 5 
         2 4 5 
         3 4 5

但是，当我使用 JS 尝试这段代码时，我没有得到预期的输出：

let ans = [],
  arr = [];

function makeCombination(n, k, low = 1) {
  if (k == 0) {
    ans.push(arr);
    console.log(...arr);
    return;
  }

  for (let i = low; i <= n; i++) {
    arr.push(i);
    makeCombination(n, k - 1, i + 1);
    arr.pop();
  }
  return ans;
}

var n = 5;
var k = 3;

makeCombination(n, k);

输出：

1 2 3
1 2 4
1 2 5

你能帮忙吗，为什么我没有得到预期的输出？如果您能提供帮助，我将不胜感激。

Answer 1

let ans = [],
  arr = [];

function makeCombination(n, k, low = 1) {
  if (k == 0) {
    ans.push(arr.slice());
//    console.log(...arr); commenting out the console log to demonstrate that the returned value is correct
    return;
  }

  for (let i = low; i <= n; i++) {
    arr.push(i);
    makeCombination(n, k - 1, i + 1);
    arr.pop();
  }
  return ans;
}

var n = 5;
var k = 3;

makeCombination(n, k).map(a => console.log(...a));

.as-console-wrapper { max-height: 100% !important; top: 0; }

您需要复制部分结果数组。否则，您将对同一数组的引用推送到结果数组，并在回溯算法期间从中删除元素。

问题的一个明显迹象是您的函数向控制台写入了正确的结果，但返回的结果数组填充了空数组。使用 slice() 制作副本可避免此问题。

编辑：复制了 Nina Scholz 的控制台格式化技术，因为它看起来好多了。

Answer 2

除了在函数之外使用一些其他变量外，您还可以使用一个 returns 单个数组的函数。

function makeCombination(n, k, i = 1) {
    const result = [];
    while (i <= n - k + 1) {
        if (k === 1) result.push([i]);
        else result.push(...makeCombination(n, k - 1, i + 1).map(a => [i, ...a]));
        i++;
    }
    return result;
}

makeCombination(5, 3).map(a => console.log(...a));

.as-console-wrapper { max-height: 100% !important; top: 0; }

组合问题 - 给定两个整数 n 和 k，编写一个程序 return 1 2 3 n 中 k 个数字的所有可能组合

Combination problem - Given two integers n and k, write a program to return all possible combinations of k numbers out of 1 2 3 n

javascript

algorithm

combinations