JavaScript如何正确调用Combinational Sum I算法并编写测试

现有代码的已知问题 #

• 未对输入的target做整数转换：从input拿到的value是字符串类型，直接传入函数会导致数值判断逻辑异常
• 拼写错误：递归循环里的candidates.lenght属性名拼写错误，正确写法是candidates.length，这个错误会导致循环不执行，永远返回空数组
• 数组转换逻辑冗余：额外写的for循环做整数转换属于重复操作，split(' ').map(Number)已经完成了字符串转数字的逻辑，而且直接用split(' ')无法处理多个空格分隔的输入，容易产生NaN值
• 未做DOM加载判断：如果script标签放在HTML的head区域，会在DOM渲染完成前执行getElementById，拿到null值导致绑定点击事件报错

函数正确调用方式 #

首先要确保script正确引入：

把script标签放在HTML的</body>闭合标签之前引入，或者把DOM操作逻辑包裹在document.addEventListener('DOMContentLoaded', () => { /* 逻辑 */ })中，保证执行时DOM元素已经加载完成。

函数入参要求：

• 第一个参数candidates：由正整数组成的一维数组，注意如果数组有重复值需要先去重，否则会返回重复的组合
• 第二个参数target：正整数类型的目标和

调用示例：

// 直接调用示例
const res = combinationalSum([2,3,6,7], 7);
console.log(res); // 输出 [[2,2,3],[7]]

算法核心计算逻辑 #

这个函数用深度优先搜索(DFS)+回溯的思路实现，逻辑流程如下：

1. 初始化空的结果数组，存储所有符合要求的组合，先对候选数组做升序排序，配合固定起始索引的遍历规则，避免出现内容相同顺序不同的重复组合
2. 定义内部递归函数dfs，接收4个参数：当前遍历的起始索引i、候选数组、剩余需要凑的目标值、当前已拼接的组合路径slate
   • 剪枝判断：如果剩余目标值小于0，说明当前路径的和已经超过目标，直接终止递归返回
   • 终止判断：如果剩余目标值等于0，说明当前路径的和刚好匹配目标，把当前路径做浅拷贝后存入结果数组，终止递归返回
   • 递归遍历：从起始索引i开始遍历候选数组，把当前元素压入路径，递归调用dfs——因为允许重复选取同一个元素，下一轮递归的起始索引依然是当前元素的索引j，同时把剩余目标值减去当前元素的值；递归返回后，把当前元素从路径中弹出，完成回溯操作，遍历下一个元素
3. 从索引0、空路径、初始目标值启动递归，所有递归执行完成后返回结果数组

修复后的完整可运行代码 #

HTML页面结构示例：

<!-- 页面结构 -->
<div>
  <label>输入候选数字（空格分隔）：</label>
  <input type="text" id="input" placeholder="例如：2 3 6 7">
</div>
<div>
  <label>输入目标和：</label>
  <input type="number" id="target" placeholder="例如：7">
</div>
<button id="botun">计算组合</button>
<div id="result"></div>
<!-- 把script放在body末尾引入 -->
<script src="script.js"></script>

修复后的script.js代码：

document.addEventListener('DOMContentLoaded', () => {
  const botun = document.getElementById('botun');
  const inputEl = document.getElementById('input');
  const targetEl = document.getElementById('target');
  const resultEl = document.getElementById('result');

  botun.onclick = function(){
    // 处理输入：按空格分割，过滤空值，转数字
    const numArr = inputEl.value.trim().split(/\s+/).filter(Boolean).map(Number);
    // 目标值转整数
    const target = parseInt(targetEl.value, 10);
    
    // 简单输入校验
    if (numArr.some(isNaN) || isNaN(target)) {
      resultEl.textContent = '请输入合法的数字';
      return;
    }

    // 调用函数
    const result = combinationalSum(numArr, target);
    console.log('计算结果：', result);
    // 渲染结果到页面
    resultEl.textContent = `符合要求的组合：${JSON.stringify(result)}`;
  }
})

var combinationalSum = function(candidates, target){
  const result = [];
  // 排序+去重，避免返回重复组合
  candidates = [...new Set(candidates)].sort((a,b) => a - b);

  const dfs = (i, candidates, target, slate) => {
    if (target < 0) return;
    if (target === 0) {
      result.push(slate.slice());
      return;
    }
    // 修复原拼写错误
    for(let j = i; j < candidates.length; j++){
      slate.push(candidates[j]);
      dfs(j, candidates, target - candidates[j], slate);
      slate.pop();
    }
  }
  
  dfs(0, candidates, target, []);
  return result;
};

测试方法 #

• 页面交互测试：在候选数输入框输入空格分隔的数字，目标和输入框输入整数，点击计算按钮，即可在控制台和页面看到结果，可参考以下测试用例验证正确性：
  • 输入候选数2 3 6 7，目标和7，预期输出[[2,2,3],[7]]
  • 输入候选数2 3 5，目标和8，预期输出[[2,2,2,2],[2,3,3],[3,5]]
  • 输入候选数2，目标和1，预期输出[]
• 无页面快速测试：直接在浏览器控制台/Node环境中粘贴combinationalSum函数定义，直接传参调用即可验证逻辑，不需要依赖DOM元素。

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