遞歸搜索專題：組合生成、子集和、生日西瓜分配

經典遞歸搜索模板

遞歸搜索（DFS）通過「選 / 不選」或「枚舉下一步」遍歷解空間樹，配合剪枝可解決組合、排列、子集和等問題。

1. 組合生成（NY 325）

從 1…n 中選 r 個數，每組合內降序，組合間逆字典序輸出。

void dfs(int last, int depth) {
    if (depth == r) { output(); return; }
    for (int i = last; i >= r - depth; --i) {
        ans[depth] = i;
        dfs(i - 1, depth + 1);
    }
}

2. 子集和分割（西瓜分配）

n ≤ 20，將集合分為兩堆，使重量差最小。
遞歸枚舉每個西瓜分給 A 或 B，或用 0-1 背包（總重 ≤ 20×10000=2e5）。

void dfs(int idx, int sumA) {
    if (idx == n) { ans = min(ans, abs(total - 2*sumA)); return; }
    dfs(idx + 1, sumA + w[idx]); // 分給 A
    dfs(idx + 1, sumA);          // 分給 B
}

3. 遞歸搜索剪枝技巧

• 可行性剪枝：剩餘元素全選也無法達到目標 → 返回。
• 最優性剪枝：當前已超過最佳答案 → 返回。
• 排序優化：大數優先搜索，更早觸發剪枝。

完整示例：組合生成（NY 32）

#include <bits/stdc++.h>
using namespace std;
int n, r, ans[15];
void dfs(int u, int step) {
    if (step == r) {
        for (int i = 0; i < r; ++i) cout << ans[i];
        cout << '\n'; return;
    }
    for (int i = u; i >= r - step; --i) {
        ans[step] = i;
        dfs(i - 1, step + 1);
    }
}
int main() {
    while (cin >> n >> r) dfs(n, 0);
    return 0;
}

複雜度

組合數 C(n, r)；子集和 O(2ⁿ)，n ≤ 20 可接受。