JS至多k次交换找最小值回溯算法Bug排查求助

嘿，我一眼就看到你代码里的核心问题了——JavaScript的原始类型是值传递，这直接导致递归里修改的minSoFar根本不会同步到外层函数，这就是为什么明明日志里能看到num降到159，最终返回的还是初始值951。

下面给你一步步拆解排查思路和修复方案：

1. 问题根源：值传递的坑 #

你把minSoFar作为参数传入递归函数，它是一个数字（原始类型）。每次递归调用时，传递的都是这个数值的副本，而不是引用。也就是说，递归深处修改的只是这个副本的数值，外层函数里的minSoFar完全没变化。举个例子：当你在某层递归里把minSoFar改成159，回到上一层函数时，这个修改不会被带回去，上一层的minSoFar还是之前的数值，最后自然返回初始的951。

你可以加个日志验证：在递归里修改minSoFar后打印它，同时在外层递归结束后也打印，会发现内外层的数值完全不一样，这就能坐实是值传递的问题。

2. 修复方案：让递归传递更新后的最小值 #

有两种常见的修复方式，我给你推荐最直观的一种——让递归函数返回每次递归后的最小数值，在外层把返回值赋值给当前的最小值，这样递归深处的结果就能层层传递回来。

修改后的代码如下：

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(''));
  // 先更新当前的最小值
  let currentMin = Math.min(minSoFar, num);
  
  // 基准情况：没有交换次数了，直接返回当前最小值
  if (k < 1) {
    return currentMin;
  }

  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);
        // 递归调用，并用返回的最小值更新currentMin
        currentMin = Math.min(currentMin, findMin(digits, n, k - 1, currentMin));
        // 回溯，恢复原数组
        swap(digits, i, j);
      }
    }
  }
  return currentMin;
}

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}`); // 现在会正确输出159

3. 代码修改说明 #

• 用currentMin来保存当前层级的最小值，初始时取minSoFar和当前数字的较小者。
• 每次递归调用后，把返回的最小值和currentMin比较，更新为更小的那个，确保递归深处的最小值能传递回来。
• 基准情况直接返回当前的currentMin，不再依赖参数里的minSoFar。

另外，额外提个优化点：如果当前位置已经找到最小的数字（比如i位置已经是后面所有数字里最小的），可以跳过不必要的递归，减少计算量，但这属于锦上添花，核心问题还是值传递的坑。

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