[NOIP2001 提高组] 数的划分(剪枝)

using namespace std;
const int N=1e5+10;
int a[N],res,n,k;
void prit()
{
    for(int i=1;i<k;i++) cout<<a[i]<<" ";
    cout<<a[k]<<endl;
}
void dfs(int now,int cnt)
{
    if(cnt>k||now<0) return;
    for(int i=a[cnt-1];i<=now;i++)//题目要求颠倒顺序的不算,那么就要考虑如何消除,这里就可以使用一个数组来记录上一个的值
    //如果当前不小于这个值,那么顺序就是递增的,额外提一嘴,数组此时也是储存的最小字典序的顺序;
    //这里的剪枝策略是,从不小于上一个值的位置开始,一直到现在的值
        {
            a[cnt]=i;
            if(now-i==0&&cnt==k) res++,prit();
            else dfs(now-i,cnt+1);
        }
}
int main()
{
    a[0]=1;
    cin >>n>>k;
    dfs(n,1);
    cout<<res;
    return 0;
}