#include <stdio.h>
int n;
int p[210];
int m;
bool dfs(int i, int sum) {
if (i == n) return sum == m;
if (dfs(i + 1, sum + p[i])) return true;
if (dfs(i + 1, sum)) return true;
return false;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", &p[i]);
scanf("%d", &m);
if (dfs(0, 0))
printf("1");
else
printf("0");
return 0;
}
加入剪枝（未测试）
```C++
include
int n; int p[210]; int m;
bool dfs(int i, int sum) { if (sum > m) return false; // 剪枝 if (i == n) return sum == m; if (dfs(i + 1, sum + p[i])) return true; if (dfs(i + 1, sum)) return true; return false; }
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", &p[i]);
scanf("%d", &m);
if (dfs(0, 0))
printf("1");
else
printf("0");
return 0;
}
## 2. 最优分割
<div align="center"><img src="../_assets/TIM截图20180920192513.png" height="" /></div>
**思路**
- 二分查找、动态规划
- LeetCode [410. 分割数组的最大值](https://leetcode-cn.com/problems/split-array-largest-sum/description/)
**低保**（18%）
```python
n, m = list(map(int, input().split()))
A = list(map(int, input().split()))
if sum(A) % m == 0:
print(sum(A) // m)
Python（未测试）
# 作者：Tercel818
# 链接：https://www.nowcoder.com/discuss/114578?type=2&order=0&pos=23&page=1
# 来源：牛客网
n, m = map(int, input().split())
nums = list(map(int, input().split()))
acc_sum = [0]
for item in nums:
acc_sum.append(acc_sum[-1] + item)
dp = [[float("inf")] * (1 + len(nums)) for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
for j in range(1, len(nums) + 1):
for k in reversed(range(i - 1, j)):
val = max(dp[i - 1][k], acc_sum[j] - acc_sum[k])
dp[i][j] = min(val, dp[i][j])
print(dp[m][len(nums)])
