dfs+剪枝优化

正常dfs： 注意为了去重（如{1，2，4}和{2，1，4}）用i=last保证它是唯一非递减序列

剪枝： 注意点 循环上限n可替换为（n-sum)/(k-step) 即当前的剩余和/剩余步数 如果有参数超过这个平均值必定会超过范围

#include<bits/stdc++.h>

using namespace std;

int n,k,num[200];
int ans=0;

void dfs(int last,int step,int sum){
	if(step==k){	
		if(sum==n)ans++;
		return ;		
	}
	int max_n=(n-sum)/(k-step);
	for(int i=last;i<=max_n;++i){//last 
		num[step]=i;

		dfs(i,step+1,sum+i);
		
	}
	
}

void solve(){
	cin>>n>>k;
	dfs(1,0,0);
	cout<<ans;
}

int main(){
	
	ios::sync_with_stdio(false),cin.tie(nullptr);
	int T=1;	
	while(T--){		
		solve();
	}
	return 0;
	
}