暴力搜索+剪枝+回溯

解题思路:首先可以先列深度搜索的整体代码，这时只能获得部分分数，因为暴力搜索范围很大会导致超时，然后进行剪枝操作，第一个剪枝如果n减着剪着变成了0，说明n分着分着不够用了，这条路就走不通了，回溯，第二个要剪枝是可以选择一种顺序来找，我选择的是升序，所以应该让后一个数比前一个数大，最后要注意，当递归深度和输入的k一样了，我们还要比较当前的n是否比前一个数大这样才能形成升序。

注意事项:

参考代码:

# include<iostream>//n=7,k=3,一共三层for可以选择的数是1-6 

using namespace std;

int num=0,sum=0;

int n,k;

int a[20]={1};

void dfs(int t)

{

                if(n==0)return ;//剪枝1，如果n减到0就立马返回说明此路不行 

                if(t==k)

                {

                     if(n>=a[t-1])//剪枝2 最后一个属数应该比前一个数大 

                     {

                           num++;

                      }

               return;

               } 

               for(int i=1;i<=(n-1);i++) 

               {

                      if(i>=a[t-1])//剪枝3 前几个数应该是依次递增，也就是最后一个数字比前一个大 

                     {

                             a[t]=i;

                             n-=i;//让n减去当前的数 

                             dfs(t+1);//深度搜索 

                             n+=i;//回溯 

                       }

               }

} 

int main()

{

cin>>n>>k;

dfs(1);

cout<<num;

return 0;

}