从数值对象中计算匹配目标值的加法组合

当然有不用递归的解决办法！而且不管是2数之和、3数之和，甚至是任意N数之和的场景，都能通过迭代的方式搞定。我给你一步步拆解，结合代码示例来说明：

第一步：预处理数据 #

首先把你的带键对象转换成便于处理的数组，保留键和数值的结构，这样最后能直接返回对应的键而不只是数值。举个例子，假设你的对象是：

const numObj = { a: 10, b: 20, c: 30, d: 40, e: 50 };

我们可以转成这样的数组：

const numArr = Object.entries(numObj).map(([key, val]) => ({ key, value: Number(val) }));

1. 2数之和的高效非递归实现 #

你之前用的线性遍历如果是双重循环的话，其实可以优化成哈希表（Map）的方式，时间复杂度从O(n²)降到O(n)：

function findTwoSum(target, numArr) {
  const valueMap = new Map();
  for (const item of numArr) {
    const complement = target - item.value;
    if (valueMap.has(complement)) {
      return [valueMap.get(complement).key, item.key];
    }
    valueMap.set(item.value, item);
  }
  return null; // 找不到匹配
}

// 测试：目标50
console.log(findTwoSum(50, numArr)); // 可能返回 ["b", "d"]（20+40）或者["a", "e"]（10+50）

2. 3数之和的非递归实现 #

这里用排序+双指针的思路，完全不用递归：

function findThreeSum(target, numArr) {
  // 先排序数组，方便双指针操作
  const sortedArr = [...numArr].sort((a, b) => a.value - b.value);
  const n = sortedArr.length;

  for (let i = 0; i < n - 2; i++) {
    // 跳过重复值（如果有重复数值的话）
    if (i > 0 && sortedArr[i].value === sortedArr[i-1].value) continue;
    
    const remain = target - sortedArr[i].value;
    let left = i + 1;
    let right = n - 1;

    while (left < right) {
      const currentSum = sortedArr[left].value + sortedArr[right].value;
      if (currentSum === remain) {
        return [sortedArr[i].key, sortedArr[left].key, sortedArr[right].key];
      } else if (currentSum < remain) {
        left++;
      } else {
        right--;
      }
    }
  }
  return null;
}

// 测试：目标60
console.log(findThreeSum(60, numArr)); // 比如 ["a", "b", "c"]（10+20+30）

3. 通用N数之和的非递归实现（任意数量数值相加） #

如果需要支持任意N个数相加的场景，可以用迭代式回溯（用栈模拟递归的调用栈，本质是非递归）。核心思路是逐步构建数值组合，每次添加一个新的数值，直到组合的和等于目标值，或者超过目标值就回溯：

function findNSum(target, numArr, n) {
  if (n < 2 || numArr.length < n) return null;
  
  // 排序，方便剪枝（提前终止不可能的组合）
  const sortedArr = [...numArr].sort((a, b) => a.value - b.value);
  // 用栈存储当前的组合状态：[当前索引, 当前组合, 当前和]
  const stack = [];

  // 初始化栈：每个元素作为初始组合的第一个元素
  for (let i = 0; i < sortedArr.length; i++) {
    stack.push([i, [sortedArr[i]], sortedArr[i].value]);
  }

  while (stack.length > 0) {
    const [currentIndex, currentCombo, currentSum] = stack.pop();
    
    if (currentCombo.length === n) {
      if (currentSum === target) {
        return currentCombo.map(item => item.key);
      }
      continue;
    }

    // 继续添加后续的元素，避免重复组合
    for (let i = currentIndex + 1; i < sortedArr.length; i++) {
      // 剪枝：如果当前和加上剩下的所有元素都不够目标值，直接跳过
      const remaining = n - currentCombo.length;
      const maxPossibleSum = currentSum + sortedArr[i].value * remaining;
      if (maxPossibleSum < target) continue;
      // 剪枝：如果当前和加上当前元素已经超过目标值，后面的更大，直接break
      if (currentSum + sortedArr[i].value > target) break;

      stack.push([
        i,
        [...currentCombo, sortedArr[i]],
        currentSum + sortedArr[i].value
      ]);
    }
  }

  return null;
}

// 测试：目标60，找3个数之和
console.log(findNSum(60, numArr, 3)); // 同样能找到["a", "b", "c"]
// 测试：目标100，找4个数之和（10+20+30+40）
console.log(findNSum(100, numArr, 4)); // 返回["a", "b", "c", "d"]

这些方法都是纯迭代实现，完全不需要递归调用，而且通过排序、剪枝、哈希表等技巧优化了时间复杂度，比单纯的暴力遍历高效很多。如果你的对象里有重复数值，还可以在代码里加上去重逻辑，避免返回重复的组合。

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