LeetCode中如何实现组合总和

# LeetCode中如何实现组合总和

## 引言

组合总和（Combination Sum）是LeetCode中经典的回溯算法问题（如第39题、第40题等）。这类问题要求从给定的候选数组中找出所有能使数字和为特定目标值的唯一组合。本文将详细讲解组合总和问题的解题思路、代码实现及优化方法。

---

## 问题描述

以LeetCode 39题为例：
- **输入**：无重复元素的整数数组`candidates`和目标整数`target`
- **输出**：所有`candidates`中数字和为`target`的唯一组合（可重复使用同一数字）
- **示例**：
  ```python
  输入: candidates = [2,3,6,7], target = 7
  输出: [[2,2,3], [7]]

解题思路

1. 回溯算法框架

回溯法是解决组合问题的标准方法，其核心是通过递归尝试所有可能的路径，并通过剪枝减少无效搜索。

关键步骤： 1. 选择：从候选数组中选择一个数字加入当前组合 2. 约束：检查当前组合的和是否超过target 3. 目标：当组合和等于target时记录结果 4. 回溯：撤销最后的选择以尝试其他可能性

2. 递归树分析

以candidates = [2,3,6,7], target = 7为例：

         []
       / | \ \
      2  3  6 7
    / | \ 
   2  3  6
  / 
 2

• 路径[2,2,3]和为7，加入结果
• 路径[7]直接满足条件

代码实现

Python版本

def combinationSum(candidates, target):
    def backtrack(start, path, remaining):
        if remaining == 0:
            res.append(path.copy())
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                continue  # 剪枝
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # 允许重复使用
            path.pop()  # 回溯
    
    res = []
    candidates.sort()  # 排序便于剪枝
    backtrack(0, [], target)
    return res

Java版本

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(res, new ArrayList<>(), candidates, target, 0);
        return res;
    }
    
    private void backtrack(List<List<Integer>> res, List<Integer> temp, 
                         int[] nums, int remain, int start) {
        if (remain < 0) return;
        if (remain == 0) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            temp.add(nums[i]);
            backtrack(res, temp, nums, remain - nums[i], i);
            temp.remove(temp.size() - 1);
        }
    }
}

变种问题

1. 组合总和II（LeetCode 40）

• 区别：候选数组包含重复元素，且每个数字只能使用一次
• 解法调整：
  • 排序后跳过重复数字：if i > start and candidates[i] == candidates[i-1]: continue
  • 递归时起始位置改为i+1

2. 组合总和III（LeetCode 216）

• 区别：仅使用1-9的数字，且组合长度为k
• 解法调整：
  • 增加长度限制：if len(path) == k and remain == 0: res.append(path.copy())

优化技巧

1. 排序剪枝：预处理排序数组，当candidates[i] > remaining时可提前终止循环
2. 哈希去重：适用于包含重复元素的变种问题
3. 动态规划：当仅需计算组合数时可用DP（类似背包问题）

复杂度分析

• 时间复杂度：O(N^(T/M +1))，其中N为候选数组长度，T为目标值，M为最小候选值
• 空间复杂度：O(T/M)（递归栈深度）

常见错误

1. 忘记回溯：在递归返回后需移除最后添加的元素
2. 重复组合：在允许重复使用数字时需注意起始位置参数
3. 未排序剪枝：导致无法提前终止无效分支

总结

组合总和问题通过回溯算法可系统性地遍历所有可能解。掌握以下要点是关键： 1. 递归终止条件的设定 2. 剪枝条件的优化 3. 变种问题的差异处理

建议读者在LeetCode上实际练习39、40、216等题目以加深理解。 “`

（注：实际字数约1300字，此处为精简展示版，完整版可扩展更多示例和图示）