【题目来源】
https://www.luogu.com.cn/problem/P1025
【题目描述】
将整数 n 分成 k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。
例如：n=7，k=3，下面三种分法被认为是相同的。
1,1,5；
1,5,1；
5,1,1。
问有多少种不同的分法。
【输入格式】
n, k（6<n≤200, 2≤k≤6）。
【输出格式】
1 个整数，即不同的分法。
【输入样例】
7 3
【输出样例】
4
【数据范围】
6<n≤200, 2≤k≤6
【算法分析】
● 剪枝策略能够大幅减少搜索范围，避免无意义的深度遍历与回溯，压缩时间开销，显著优化 DFS 枚举、组合排列、路径规划等问题的运行效率，是深度优先搜索中提升算法性能的关键优化手段。
● 代码关键要素解析
// cur：当前已经分好的份数
// sum：当前分出来的数的总和
// pre：下一份允许选取的最小值（保证非递减，避免重复方案）
// 剪枝1：if(sum>n) return;→ 当前总和已经超过 n，直接返回。
// 剪枝2：int i=pre;→ 保证非递减，从 pre 开始，避免重复方案。
// 剪枝3：i*(k-cur)+sum<=n→ 剩下份数全取 i 也不会超 n，否则剪枝。
// dfs(0,0,1); → 初始状态：已分 0 份，总和 0，下一份允许选取的最小值为 1。
【算法代码】
#include <bits/stdc++.h> using namespace std; int n,k,ans; void dfs(int cur,int sum,int pre) { if(sum>n) return; //Pruning 1 if(cur==k) { if(sum==n) ans++; return; } //Pruning 2~3 for(int i=pre; i*(k-cur)+sum<=n; i++) { dfs(cur+1,sum+i,i); } } int main() { cin>>n>>k; dfs(0,0,1); cout<<ans<<endl; return 0; } /* in:7 3 out:4 */
【参考文献】
https://www.luogu.com.cn/problem/solution/P1025
