原题 传送门
【题目描述】
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5； 1，5，1； 5，1，1；
问有多少种不同的分法。 输出一个整数，即不同的分法。
【输入】
两个整数n，k(6<n≤200，2≤k≤6)，中间用单个空格隔开。
【输出】
一个整数，即不同的分法。
【输入样例】
7 3
【输出样例】
4
【提示】
四种分法为：1，1，5；1，2，4；1，3，3；2，2，3。
本题就是求把数字n无序划分成k份的方案数。也就是求方程X1+X2+……Xk=n，1<=X1<=X2<=……Xk的解数。
搜索的方法是依次枚举X1,X2,……Xk的值，然后判断，如果这样一直直接搜索，程序的运行速度是非常慢的。但由于本题的数据规模比较小，如果控制好扩展结点的上界和下界，也是能够很快得出解的。
约束条件：
1.由于分解数不考虑顺序，因此我们设定分解数依次递增，所以扩展点时的下界应该是不小于前一个扩展点的值，即a[i-1]<=a[i]；
2.假设我们将n已经分解成了a[1]+a[2]+……+a[i-1]，则a[i]的最大值为i~k这k-i+1分平均划分，即设m=n-（a[1]+a[2]+……+a[i-1]），则a[i]<=m/（k-i+1），所以扩展点的上界是m/（k-i+1）；
代码如下：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int read() { char ch=getchar(); int a=0,x=1; while(ch<'0'||ch>'9') { if(ch=='-') x=-x; ch=getchar(); } while(ch>='0'&&ch<='9') { a=(a<<3)+(a<<1)+(ch-'0'); ch=getchar(); } return a*x; } int n,m,a[9],s=0; void dfs(int x) { if(n==0) return ; //若将n分解完，则直接返回 if(x==m) //若此时分解数的个数到了m { if(n>=a[x-1]) s++; return ; } for(int i=a[x-1];i<=n/(m-x+1);i++) //从下界枚举到上界 { a[x]=i; n-=i; dfs(x+1); n+=i; //回溯 } } int main() { n=read(); m=read(); a[0]=1; //从1开始分解 dfs(1); cout<<s<<endl; return 0; }
对神搜的剪枝技巧进行小结：
所谓剪枝就是通过某种判断，避免一些不必要的遍历过程，形象地说，就是减去搜索树中的某些枝条，故城剪枝。
剪枝的原则：
1.正确性；
2.准确性；
3.高效性；
深度优先搜索的优化技巧：
1.优化搜索顺序；
2.排除等效冗杂；
3.可行性剪枝；
4.最优性剪枝；
5.记忆化；