🧠 Python小练习系列 Vol.8：组合总和（回溯 + 剪枝 + 去重）
💡 本期我们挑战 LeetCode 回溯题三件套之一 —— 组合总和，深入掌握路径构建、剪枝策略与去重技巧！
🧩 一、题目描述
给定一个无重复正整数数组 candidates 和一个目标值 target，找出所有和为 target 的组合。每个数可以重复使用无限次。
示例：
输入: candidates = [2,3,6,7], target = 7
输出: [[2,2,3], [7]]
🧠 二、解题思路
我们采用回溯算法 + 剪枝：
- 尝试将
candidates[i]加入当前组合路径； - 若路径之和超过
target，立即剪枝； - 每次递归从当前下标开始，允许重复使用数字；
- 当路径之和正好等于
target，加入结果集。
👨💻 三、Python代码实现
def combination_sum(candidates, target):res = []path = []def dfs(start, total):if total == target:res.append(path[:])returnif total > target:returnfor i in range(start, len(candidates)):path.append(candidates[i])dfs(i, total + candidates[i]) # 允许重复取，索引不变path.pop()dfs(0, 0)return res
📌 四、运行示例
print(combination_sum([2, 3, 6, 7], 7))
# 输出：[[2, 2, 3], [7]]
🧩 五、解题小结
| 步骤 | 说明 |
|---|---|
| 递归结构 | 当前索引 + 当前路径和 |
| 剪枝条件 | 如果 total > target，立即 return |
| 去重策略 | 控制递归起点，避免重复排列组合 |
✅ 本题是“回溯选数”类题目的标准模板。
💡 六、进阶挑战
- 📦 如果数组中可能有重复数字，如何避免结果重复？（组合总和 II）
- 🧠 只能使用每个数字一次，怎么改动递归逻辑？
- 🚀 如果要求找出总和为 target 的最短组合呢？
❤️ 结语
组合总和不仅考验回溯技巧，更是刷题进阶路上的重要关卡，搞懂它，下一题你会更轻松！
👉 点个赞 👍 + 收藏 🌟，我们下期再战算法高地！
