题目大意

给定 $N$ 个物品（比赛门票）的价格和总预算 $M$，求选择若干物品（可以不选）使得总价格不超过 $M$ 的方案数。

算法思路

核心思想

折半搜索（Meet in the Middle），将大问题分成两个子问题分别求解再合并。

关键观察

直接枚举所有 $2^N$ 种方案在 $N \leq 40$ 时不可行

将物品分成两半后，每半最多 $2^{20}$ 种方案，可以接受

分别计算两半的所有可能子集和，再通过双指针统计组合数

算法步骤

1. 数据划分

将 $N$ 个物品分成近似相等的两部分

第一部分：后 $\lfloor N/2 \rfloor$ 个物品

第二部分：前 $\lceil N/2 \rceil$ 个物品

2. 分别搜索

对第一部分进行 DFS，记录所有可能的子集和到 v1[]

对第二部分进行 DFS，记录所有可能的子集和到 v2[]

3. 排序与统计

对 v1[] 和 v2[] 分别排序

使用双指针法：

指针 p1 从小到大遍历 v1

指针 p2 从大到小遍历 v2

对于每个 v1[p1]，找到最大的 p2 使得 v1[p1] + v2[p2] <= M

累加 p2 到答案中

算法流程

读入数据：$N$, $M$ 和价格数组

排序价格：便于后续处理

折半搜索：

dfs1：处理后半部分物品

dfs2：处理前半部分物品

排序子集和：为双指针做准备

双指针统计：计算有效组合数

输出结果

复杂度分析

时间复杂度：$O(2^{N/2} + 2^{N/2} \log 2^{N/2}) = O(2^{N/2} \cdot N)$

空间复杂度：$O(2^{N/2})$，存储子集和数组

总结

本题是折半搜索的经典应用：

问题分解：将指数级问题降为两个平方根级问题

DFS 枚举：递归生成所有可能的子集和

排序优化：通过排序 enabling 双指针统计

组合计数：利用有序数组快速统计有效组合

这种"分治 + 双指针"的方法适用于许多子集和计数问题，特别是在 $N$ 较大但可折半处理时非常有效。