蓝桥杯备考：DFS剪枝之数的划分
这道题和组合型枚举差不多，比如我们从第一个数开始填，到第二个数的时候，21明显是重复了，我们就没必要继续往下递归了，这个叫剪掉等效冗余分支，然后还有就是，比如我们2开始的枝头，222，223，224，225，我们222的时候就已经比5大了，这时候我们再递归算后面的就没用了，我们3开始的时候，344，345肯定是更大的了 所以这条就是我们的可行性剪枝，我们把后面的分支全部剪掉就行了
#include <iostream>
using namespace std;
int n,k;
int path;
int cnt;
void dfs(int pos,int begin)
{
if(pos == k)
{
if(path == n)
cnt++;
return;
}
for(int i = begin;i<=n;i++)
{
if(path+i*(k-pos)>n) return;
path+=i;
dfs(pos+1,i);
path-=i;
}
}
int main()
{
cin >> n >> k;
dfs(0,1);
cout << cnt << endl;
return 0;
}