组合

副标题 / 摘要 组合总和是 Hot100 回溯阶段里第一道真正把“组合模板 + 目标约束 + 排序剪枝”揉在一起的题。你不应该直接背结论，而应该顺着问题一步步推出：为什么要有 path，为什么要有 remain，为什么下一层仍然从 i 开始。 预计阅读时长：14~16 分钟 标签：Hot100、回溯、组合、剪枝 SEO 关键词：Combination Sum, 组合总和, 回溯, 剪枝, remain, DFS 元描述：通过 LeetCode 39 建立组合型回溯加剪枝模板，理解可重复选取、remain 语义与排序后的安全剪枝。 A — Algorithm（题目与算法） 题目还原 给定一个无重复元素的整数数组 candidates 和一个目标整数 target， 找出 candidates 中所有可以使数字和为 target 的不同组合，并以列表形式返回。 你可以无限次选取同一个候选数字。 如果两个组合中某个数字出现次数不同，则它们被视为不同组合。 输入输出 名称 类型 描述 candidates int[] 无重复元素的候选数组 target int 目标和 返回 int[][] 所有和为 target 的不同组合 示例 1 输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 示例 2 输入：candidates = [2,3,5], target = 8 输出：[[2,2,2,2],[2,3,3],[3,5]] 示例 3 输入：candidates = [2], target = 1 输出：[] 约束 1 <= candidates.length <= 30 2 <= candidates[i] <= 40 candidates 中所有元素互不相同 1 <= target <= 40 官方保证满足条件的不同组合数少于 150 目标读者 已经做过 78. 子集，现在准备学习“带目标约束”的回溯写法 知道回溯大概长什么样，但一碰到“数字可重复选取”就容易写错边界的学习者 想把这题真正写成模板，而不是只记住 dfs(i, remain - x) 这一行的开发者 背景 / 动机 39. 组合总和 很适合作为回溯第二阶段的训练题，因为它让你同时处理三件事： ...

副标题 / 摘要 继承容易让系统变脆，组合让系统更灵活。本文解释为什么组合更适合工程演进，并给出实用示例。 目标读者 写面向对象代码的工程师 负责模块演进与重构的开发者 做代码评审与架构设计的团队 背景 / 动机 继承会把父类的实现细节暴露给子类，容易导致“脆弱基类问题”。 组合通过“把能力作为对象注入”来降低耦合，更易测试与替换。 核心概念 继承（Inheritance）：is-a 关系，强耦合 组合（Composition）：has-a 关系，弱耦合 脆弱基类问题：父类改动导致子类行为改变 实践指南 / 步骤 优先建接口，延后继承 把可变行为抽成组件 用组合注入行为 通过依赖替换实现测试 只在“稳定共性”时使用继承 可运行示例 class Logger: def log(self, msg: str) -> None: print(msg) class FileSaver: def save(self, data: str) -> None: print("save", data) class ReportService: def __init__(self, logger: Logger, saver: FileSaver): self.logger = logger self.saver = saver def run(self, data: str) -> None: self.logger.log("start") self.saver.save(data) self.logger.log("done") if __name__ == "__main__": svc = ReportService(Logger(), FileSaver()) svc.run("report") 解释与原理 组合让行为可替换（如 Logger 可以换成 Mock）。 继承则把依赖固定在父类上，一旦父类变化，子类难以控制影响。 ...