题解 | #牛群分组II#

题目考察的知识点

1. 回溯法：题目要求找出数组中可以使编号和为目标数的所有不同组合，回溯法是一种常用的解决组合问题的算法。它通过不断试探和回溯的方式，找出符合条件的组合。在本题中，通过递归调用回溯函数，在每一层选择当前数字并更新目标值，然后进入下一层递归，再根据目标值的变化进行回溯撤销操作。

2. 数组排序：题目要求返回的组合按升序排序，所以在解决问题之前需要对数组进行排序。这样可以方便地排除重复组合，即如果当前数字和上一个数字相同，则跳过。

3. 组合和剪枝：在回溯过程中，通过判断当前数字是否大于目标值，可以进行剪枝操作，即直接跳出循环，无需继续遍历后面的数字。这是因为数组已经排序，如果当前数字已经大于目标值，那么后续的数字肯定也大于目标值，无法凑成组合。

题目解答方法的文字分析

该函数的名字是 cowCombinationSum2，接受两个参数 candidates 和 target。函数的目标是将 candidates 中的数字进行组合，使得组合的数字之和等于 target。函数返回一个列表，其中包含所有符合条件的组合，并按升序排序。

在函数主体内，首先对 candidates 数组进行排序，然后定义一个空数组 result 用于存放结果。接下来调用 backtrack 函数进行回溯计算，传入参数分别是 candidates，target，空数组 combination，和起始索引 start。

对于 backtrack 函数，首先判断如果 target 等于 0，即已经找到一个符合条件的组合，那么将当前组合加入结果列表 result。然后进入循环，从 start 索引开始遍历 candidates 数组。在循环内部，首先进行重复组合的判断，如果当前数字和上一个数字相同，则跳过当前循环。然后再判断当前数字是否大于目标值，如果是，则无法凑成组合，进行剪枝并跳出循环。如果上述两个条件都不满足，说明当前数字可以加入组合，将其添加到 combination 数组中，并递归调用 backtrack 函数，传入更新后的目标值和下一个索引值。递归完成后，进行回溯操作，即将当前数字从组合中移出。最后，整个函数结束后，返回结果列表 result。

本题解析所用的编程语言

本题采用的编程语言是 JavaScript。

完整且正确的编程代码

function cowCombinationSum2(candidates, target) {
  candidates.sort((a, b) => a - b); // 将候选数组按升序排序
  const result = [];
  backtrack(candidates, target, [], 0, result);
  return result;
}

function backtrack(candidates, target, combination, start, result) {
  if (target === 0) {
    result.push([...combination]); // 找到一个符合条件的组合，加入结果列表
    return;
  }

  for (let i = start; i < candidates.length; i++) {
    if (i > start && candidates[i] === candidates[i - 1]) {
      // 避免重复组合，如果当前数字和上一个数字相同，则跳过
      continue;
    }

    if (candidates[i] > target) {
      // 当前数字大于目标值，无法凑成组合，剪枝
      break;
    }

    combination.push(candidates[i]); // 将当前数字加入组合
    backtrack(candidates, target - candidates[i], combination, i + 1, result); // 递归回溯
    combination.pop(); // 回溯，将当前数字移出组合
  }
}