JS回溯算法求k次交换最小数存在Bug，请求排查

我看到你遇到的问题了——明明递归过程中已经生成了更小的数字（比如159），但最终返回的minSoFar还是初始值，这是JavaScript中基本类型传递的典型坑，咱们一步步来解决：

问题核心：基本类型的按值传递 #

你的代码里minSoFar是number类型的基本值，在递归调用findMin(digits, n, k - 1, minSoFar)时，传递的是当前minSoFar的副本。递归函数内部更新的只是这个副本，外层函数的minSoFar完全不受影响，所以最后返回的还是最初传入的951。

修正方案：让递归返回更新后的最小值 #

我们可以修改递归逻辑，让每次递归调用都返回当前分支下找到的最小值，然后外层把这个返回值赋值给minSoFar，这样就能同步更新了。修改后的代码如下：

function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function findMin(digits, n, k, minSoFar) {
  const num = parseInt(digits.join(''));
  // 更新当前的最小值
  if (num < minSoFar) {
    minSoFar = num;
  }
  // 基准情况：没有交换次数了，返回当前最小值
  if (k < 1) {
    return minSoFar;
  }

  for (let i = 0; i < n - 1; i++) {
    for (let j = i + 1; j < n; j++) {
      if (digits[i] > digits[j]) {
        swap(digits, i, j);
        // 关键：把递归返回的最小值赋值给minSoFar，同步外层变量
        minSoFar = findMin(digits, n, k - 1, minSoFar);
        // 回溯，恢复原数组状态
        swap(digits, i, j);
      }
    }
  }
  return minSoFar;
}

let i = 951;
let k = 2;
let digits = Array.from(String(i), Number);
let minimum = findMin(digits, digits.length, k, i);
console.log(`The minimum number formed by doing at most ${k} swaps is ${minimum}`);

关键修改点 #

• 递归调用时，将返回的结果重新赋值给minSoFar：minSoFar = findMin(...)，这样外层函数就能获取到内层递归找到的更小值
• 确保每次递归分支结束后，都返回更新后的minSoFar

现在运行这段代码，输入951、k=2时，就能正确返回159了。另外补充一个小优化：如果当前数字已经是当前分支下的最小值，可以提前剪枝，减少不必要的递归，但这个是锦上添花的操作，核心问题已经解决啦。

内容的提问来源于stack exchange，提问作者Robin Andrews