9. 回溯与剪枝

习题

#30901

⚡4⏳3

给定一组非负整数，使用回溯统计元素和等于 target 的下标子集数量：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool count_subsets_with_sum(
    const uint64_t *items,
    size_t count,
    uint64_t target,
    uint64_t *out_count
);

要求：

1. 每个位置最多选择一次；相同数值但位置不同的元素仍视为不同选择。
2. count == 0 时，只有 target == 0 的空子集计数为 1；数组指针可以为 NULL。
3. 使用回溯，并利用非负性在当前和超过 target 时剪枝。
4. 计数加法溢出、参数无效时返回 false，输出对象保持不变；分析最坏时间复杂度。

#30902

⚡5⏳4

实现枚举一组互不相同整数的全部排列：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef bool (*PermutationVisitor)(
    const int64_t *items,
    size_t count,
    void *context
);

bool enumerate_permutations(
    int64_t *items,
    size_t count,
    PermutationVisitor visit,
    void *context
);

要求：

1. 通过交换或标记已使用位置进行回溯；每个完整排列只访问一次。
2. visit 返回 false 时立即停止枚举，但函数返回前必须把 items 恢复为调用前的顺序。
3. 参数无效时返回 false；count == 0 时应访问一次空排列。
4. 不复制整棵搜索树，额外空间复杂度应为 $O(n)$（不计调用方提供的数组），并说明递归深度。

#30903

⚡5⏳4

使用回溯求 n 皇后问题的解数量：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool n_queens_count(
    size_t n,
    uint64_t *out_count
);

要求：

1. 每行、每列以及两条对角线至多放置一个皇后。
2. n == 0 时空棋盘有 1 个解；n 过大导致位掩码或计数无法表示时返回 false。
3. 使用列、主对角线和副对角线的占用信息剪枝，不得枚举完整排列后再逐一检查。
4. 说明状态恢复顺序，并给出 $n=1$ 到一个适合本实现测试的上界的结果。