画搜索树，学会选择、剪枝与回溯
这一课只练一件事：把每一步的选择画成 ，用 逐条走完。必会：判断安全的 条件、写完一条分支后正确 、写出停止搜索的边界。最小示例：从 3 个数 1、2、3 中选出若干个，使它们的和恰好等于 target = 4；每个数只能选或不选，1 <= n <= 20。样例追踪：选 1、跳过 2、选 3，和为 1 + 3 = 4，命中后记录方案并回溯，继续尝试其他组合。边界是 n=1（只判断这一个数是否等于 target），以及所有数都试完仍未凑出 target（无解，回溯到底）。建议掌握：统计一共找到几种方案。多维状态剪枝、双向搜索、记忆化是拓展。这里不会在浏览器里运行 C++。
任务 1：先选出搜索该怎么想、剪枝怎么判断
是搜索题的骨架。 要先想清楚安全条件。点不认识的词可看基础解释。
必会：能说出搜索题要先画搜索树、再判断剪枝条件。这里不会在浏览器里运行 C++，只练习选择和走过程。
搜索题在本课要做什么？搜索思路 · 必会
剪枝要怎么处理？剪枝 · 必会
任务 2：按选择、剪枝、回溯三步走一遍搜索树
最小示例：从 1、2、3 中选出若干个数，使和恰好等于 target = 4。按顺序点三步：先 一个数加入集合，再用 判断当前和有没有超过 target，最后 撤销选择，继续尝试别的选法。这里不会在浏览器里运行 C++。
必会：能解释每一步为什么这样做。边界：不要跳过回溯这一步。n 最多 20 时，2 的 n 次方种选法仍能在时限内枚举完。
- // 选择：把 1 加入集合，sum = 0 + 1 = 1
- // 选择：跳过 2，把 3 加入集合，sum = 1 + 3 = 4
- // 剪枝判断：sum == target，命中，记录方案
- // 回溯：撤销 3 和 1，集合清空，继续尝试其他组合
三步走完了，现在把搜索树上的判断落成一行代码：数字都是正数，一旦当前和超过 target，这条分支就不可能再凑出来，用 把它停掉。下面是只读脚手架，只留一空给你敲键盘；这里不会在浏览器里运行 C++。
- // a[1..n] 是候选数字，ans 统计能凑出 target 的方案数
- int a[25], n = 3, target = 4, ans = 0;
- void dfs(int i, int sum) {
- if (sum == target) { ans += 1; } // 刚好凑出 target：记下一种方案
- if (i > n) return; // 数字都试完了，这条分支结束
- // 剪枝：再往下选只会更大，先停
- dfs(i + 1, sum + a[i]); // 选第 i 个数字
- dfs(i + 1, sum); // 不选第 i 个数字
- }
if (sum > target) return; // 数字都是正数：当前和超过 target，再往下选只会更大
任务 3：确定处理思路，并认出两个边界
建议掌握：统计一共找到几种方案，认出边界情况。n=1 时，输入 4，只需判断这一个数是否等于 target；所有数都试完仍未凑出 target 时，说明这条路无解，回溯到上一层继续。多维状态剪枝、双向搜索、记忆化是拓展。
必会 / 建议掌握 / 拓展：必会是画搜索树、写出剪枝条件、正确回溯。建议掌握是统计方案总数。多维状态剪枝、双向搜索、记忆化是拓展，现在不用当硬门槛。
- // 思路：对每个数选或不选，递归到底后判断 sum 是否等于 target
- // 边界 1：n=1，只有一个数 4，判断它是否等于 target
- // 边界 2：所有数都试完仍未命中，无解，回溯到上一层
- // 双向搜索 / 记忆化是拓展
先选出这题该用什么处理思路：
再选出两个边界：
任务 4：随机小测，看看你是否真的懂了
每次从本课题库抽出三道不同的选择题。题目与解析已通过校验，答完后看解析，不要只看分数；拿不准就回到对应任务再看一遍。