https://www.luogu.org/problemnew/show/P1025
一道简单的dfs题，但是需要剪枝，否则会TLE。
我们用dfs(a,u,num)来表示上一个数为a，已经搜索完了a个数，现在的和是num。
1 #include<iostream> 2 using namespace std; 3 int n,k,a; 4 long long ans; 5 void dfs(int a,int u,int now){ 6 if(now>n) return; 7 if(u>k) return; 8 if(u==k){ 9 if(now==n) ans++; 10 return; 11 } 12 for(int i=a;i<=n;i++){ 13 dfs(i,u+1,now+i); 14 } 15 } 16 int main(){ 17 cin>>n>>k; 18 dfs(1,0,0); 19 cout<<ans; 20 return 0; 21 }
1 #include<iostream> 2 using namespace std; 3 int n,k,a; 4 long long ans; 5 void dfs(int a,int u,int now){ 6 if(now>n) return;//边界 7 if(u>k) return; 8 if(u==k){ 9 if(now==n) ans++; 10 return; 11 } 12 for(int i=a;now+i*(k-u)<=n;i++){//剪枝 13 dfs(i,u+1,now+i); 14 } 15 } 16 int main(){ 17 cin>>n>>k; 18 dfs(1,0,0); 19 cout<<ans; 20 return 0; 21 }
//NOIP2001提高组 t2
原文：https://www.cnblogs.com/yinyuqin/p/10883639.html
