1. 概述
在计算机科学中，一个经典问题是：从一组数字中找出一个子集，使其和尽可能接近但不超过给定的目标数 K。
我们将讨论这个问题的两个版本：
- 任意数量的数字组合
- 必须选择 M 个数字的组合
并分别给出三种解决方案：
- 回溯法（Backtracking）
- 动态规划（Dynamic Programming）
- 分治法（Meet-in-the-Middle）
最后会对比各方案的优缺点和适用场景。
2. 问题定义
我们有一个整数数组 A，长度为 N，和一个目标数 K。任务是从数组中选出一个子集，使其和尽可能接近 K，但不能超过 K。
两个版本的区别：
- 版本 1（任意数量）：可以选任意个数的元素，只要总和尽可能接近 K。
- 版本 2（指定数量）：必须选 M 个元素，它们的总和尽可能接近 K。
3. 任意数量元素的选择
3.1. 回溯法（Backtracking）
思路
递归尝试每个元素选或不选两种情况，最终找出总和最接近 K 的组合。
示例代码
int backtrack(int[] A, int i, int sum, int k) {
if (sum > k) return 0;
if (i == A.length) return sum;
int pick = backtrack(A, i + 1, sum + A[i], k);
int leave = backtrack(A, i + 1, sum, k);
return Math.max(pick, leave);
}
特点
- 时间复杂度：✅
O(2^N) - 空间复杂度：✅
O(N)（递归栈） - 可扩展：支持是否允许重复选取元素（只需修改递归参数）
⚠️ 注意：该方法在 N 较大时会超时，适用于小规模数据。
3.2. 动态规划（Dynamic Programming）
思路
使用二维 DP 表格 dp[i][sum] 来记录当前索引 i 和当前总和 sum 下的最大有效和。
示例代码
int dpApproach(int[] A, int k) {
int n = A.length;
int[][] dp = new int[n + 1][k + 1];
for (int sum = 0; sum <= k; sum++) {
dp[n][sum] = sum;
}
for (int i = n - 1; i >= 0; i--) {
for (int sum = k; sum >= 0; sum--) {
int pick = 0;
if (sum + A[i] <= k) {
pick = dp[i + 1][sum + A[i]];
}
int leave = dp[i + 1][sum];
dp[i][sum] = Math.max(pick, leave);
}
}
return dp[0][0];
}
特点
- 时间复杂度：✅
O(N * K) - 空间复杂度：✅
O(N * K) - 优点：适用于 K 较小的情况，效率高
⚠️ 注意：当 K 很大时，DP 会占用大量内存，效率反而不如回溯法。
3.3. 分治法（Meet-in-the-Middle）
思路
将数组分为两半，分别枚举所有可能的子集和，然后合并两个部分的结果。
示例代码
List<Integer> generate(int[] A, int start, int end, int sum, int k, List<Integer> res) {
if (sum > k) return res;
if (start == end) {
res.add(sum);
return res;
}
generate(A, start + 1, end, sum + A[start], k, res);
generate(A, start + 1, end, sum, k, res);
return res;
}
int meetInTheMiddle(int[] A, int k) {
int n = A.length;
List<Integer> first = new ArrayList<>();
List<Integer> second = new ArrayList<>();
generate(A, 0, n / 2, 0, k, first);
generate(A, n / 2, n, 0, k, second);
Collections.sort(second);
int result = 0;
for (int sum : first) {
int rem = k - sum;
int idx = Collections.binarySearch(second, rem);
if (idx < 0) idx = -idx - 1;
if (idx > 0) {
result = Math.max(result, sum + second.get(idx - 1));
}
}
return result;
}
特点
- 时间复杂度：✅
O(N * 2^(N/2)) - 空间复杂度：✅
O(2^(N/2)) - 优点：适用于 N 较大但 K 也较大的情况
✅ 优势：比回溯快，比 DP 更节省内存。
3.4. 支持重复选取的变种
如果允许重复选取同一个元素：
- 回溯法/DP：修改 pick 时索引不变（i 不加 1）
- 分治法：修改 generate 函数中 pick 时索引不变
3.5. 对比总结
| 方法 | 时间复杂度 | 空间复杂度 | 是否支持重复 | 适用场景 |
|---|---|---|---|---|
| 回溯法 | O(2^N) |
O(N) |
✅/❌ | N 很小 |
| 动态规划 | O(N*K) |
O(N*K) |
✅/❌ | K 很小 |
| 分治法 | O(N * 2^(N/2)) |
O(2^(N/2)) |
✅/❌ | N 中等，K 大 |
4. 指定数量元素的选择（必须选 M 个）
4.1. 回溯法（Backtracking）
思路
递归时多加一个参数 taken 表示已选元素个数。当 taken == M 时才允许返回有效值。
示例代码
int backtrackM(int[] A, int i, int sum, int taken, int m, int k) {
if (sum > k || taken > m) return 0;
if (i == A.length) {
return taken == m ? sum : 0;
}
int pick = backtrackM(A, i + 1, sum + A[i], taken + 1, m, k);
int leave = backtrackM(A, i + 1, sum, taken, m, k);
return Math.max(pick, leave);
}
特点
- 时间复杂度：✅
O(2^N) - 空间复杂度：✅
O(N)（递归栈）
4.2. 动态规划（Dynamic Programming）
思路
扩展 DP 为三维：dp[i][sum][taken]，表示当前索引、总和、已选个数下的最大有效和。
示例代码
int dpApproachM(int[] A, int k, int m) {
int n = A.length;
int[][][] dp = new int[n + 1][k + 1][m + 1];
for (int sum = 0; sum <= k; sum++) {
for (int taken = 0; taken <= m; taken++) {
dp[n][sum][taken] = (taken == m) ? sum : 0;
}
}
for (int i = n - 1; i >= 0; i--) {
for (int sum = k; sum >= 0; sum--) {
for (int taken = m; taken >= 0; taken--) {
int pick = 0;
if (sum + A[i] <= k && taken < m) {
pick = dp[i + 1][sum + A[i]][taken + 1];
}
int leave = dp[i + 1][sum][taken];
dp[i][sum][taken] = Math.max(pick, leave);
}
}
}
return dp[0][0][0];
}
特点
- 时间复杂度：✅
O(N*K*M) - 空间复杂度：✅
O(N*K*M) - 优点：适合 K、M 都不大时
4.3. 分治法（Meet-in-the-Middle）
思路
将数组分成两半，生成每个子集中选 t 个元素的所有可能和，然后合并查找互补组合。
示例代码
Map<Integer, List<Integer>> generateM(int[] A, int start, int end, int sum, int taken, int k) {
Map<Integer, List<Integer>> res = new HashMap<>();
if (sum > k) return res;
if (start == end) {
res.computeIfAbsent(taken, x -> new ArrayList<>()).add(sum);
return res;
}
Map<Integer, List<Integer>> pick = generateM(A, start + 1, end, sum + A[start], taken + 1, k);
Map<Integer, List<Integer>> leave = generateM(A, start + 1, end, sum, taken, k);
merge(res, pick);
merge(res, leave);
return res;
}
void merge(Map<Integer, List<Integer>> target, Map<Integer, List<Integer>> source) {
for (Map.Entry<Integer, List<Integer>> entry : source.entrySet()) {
target.computeIfAbsent(entry.getKey(), x -> new ArrayList<>())
.addAll(entry.getValue());
}
}
int meetInTheMiddleM(int[] A, int k, int m) {
int n = A.length;
Map<Integer, List<Integer>> first = generateM(A, 0, n / 2, 0, 0, k);
Map<Integer, List<Integer>> second = generateM(A, n / 2, n, 0, 0, k);
for (List<Integer> list : second.values()) {
Collections.sort(list);
}
int result = 0;
for (int t = 0; t <= m; t++) {
List<Integer> fList = first.getOrDefault(t, Collections.emptyList());
List<Integer> sList = second.getOrDefault(m - t, Collections.emptyList());
for (int sum : fList) {
int rem = k - sum;
int idx = Collections.binarySearch(sList, rem);
if (idx < 0) idx = -idx - 1;
if (idx > 0) {
result = Math.max(result, sum + sList.get(idx - 1));
}
}
}
return result;
}
特点
- 时间复杂度：✅
O(N * (M + 2^(N/2))) - 空间复杂度：✅
O(M * 2^(N/2)) - 优点：适用于 N 较大，M 中等的情况
4.4. 支持重复选取的变种
与任意数量版本类似：
- 修改 pick 时索引不递增（允许重复选取）
4.5. 对比总结
| 方法 | 时间复杂度 | 空间复杂度 | 是否支持重复 | 适用场景 |
|---|---|---|---|---|
| 回溯法 | O(2^N) |
O(N) |
✅/❌ | N 很小 |
| 动态规划 | O(N*K*M) |
O(N*K*M) |
✅/❌ | K、M 都不大 |
| 分治法 | O(N*(M + 2^(N/2))) |
O(M * 2^(N/2)) |
✅/❌ | N 中等，M 中等 |
5. 总结
| 问题版本 | 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| 任意数量 | 回溯法 | O(2^N) |
O(N) |
N 很小 |
| 任意数量 | 动态规划 | O(N*K) |
O(N*K) |
K 很小 |
| 任意数量 | 分治法 | O(N*2^(N/2)) |
O(2^(N/2)) |
N 中等 |
| 指定数量 | 回溯法 | O(2^N) |
O(N) |
N 很小 |
| 指定数量 | 动态规划 | O(N*K*M) |
O(N*K*M) |
K、M 都不大 |
| 指定数量 | 分治法 | O(N*(M + 2^(N/2))) |
O(M*2^(N/2)) |
N 中等，M 中等 |
✅ 建议：
- 当 N ≤ 20 时，优先用回溯法。
- 当 K 或 M 较小时，优先用动态规划。
- 当 N 较大（20~40），K 或 M 也较大时，用分治法。
⚠️ 踩坑提醒：
- DP 会占用大量内存，K 很大时慎用。
- 分治法实现复杂，调试时注意边界条件和二分查找逻辑。