algorithm-backtracking-array-sum

题目描述：
给定一个含有n个元素的整型数组a，再给定一个和sum，求出数组中满足给定和的所有元素组合，举个例子，设有数组a = [1, 2, 3, 4, 5, 6]，sum = 10，则满足和为10的所有组合是

• { 1, 2, 3, 4 }
• { 1, 3, 6 }
• { 1, 4, 5 }
• { 2, 3, 5 }
• { 4, 6 }

解题思路：

1. 核心逻辑：回溯法

• 递归尝试 ：从数组的第一个元素开始，尝试将每个元素加入当前组合。
• 撤销选择 ：如果某个元素被加入后不满足条件，则将其移除（回溯），继续尝试其他可能性。
• 终止条件 ：
  • 如果当前组合的和等于目标值 sum，记录该组合。
  • 如果当前组合的和超过目标值 sum，停止进一步尝试（剪枝）。

2. 关键点：避免重复组合
   在递归调用中，参数 start 表示当前遍历的起始位置。通过设置 start，确保每次递归只从当前元素或其后面的元素中选择，从而避免生成重复的组合。
3. 剪枝优化
   如果当前组合的和已经超过目标值 sum，则直接返回，不再继续递归。这可以显著减少不必要的计算。

代码：

function findCombinations(a, sum) {
  const result = []; // 用于存储所有满足条件的组合

  // 回溯函数
  function backtrack(start, currentCombination, currentSum) {
    // 如果当前组合的和等于目标值，记录这个组合
    if (currentSum === sum) {
      result.push([...currentCombination]); // 深拷贝当前组合
      return;
    }

    // 如果当前组合的和超过目标值，直接返回（剪枝）
    if (currentSum > sum) {
      return;
    }

    // 遍历数组，尝试将每个元素加入当前组合
    for (let i = start; i < a.length; i++) {
      currentCombination.push(a[i]); // 选择当前元素
      backtrack(i + 1, currentCombination, currentSum + a[i]); // 递归调用
      currentCombination.pop(); // 撤销选择（回溯）
    }
  }

  // 调用回溯函数
  backtrack(0, [], 0);

  return result;
}