【计蒜客-重复性剪枝】k个数的和

题目大意

从n个数中，选取k个数，使得和为sum，求选取的方案数（注意：123 和213是同一种选取方法）

解法一：

#include <iostream>
using namespace std;
int n, k, sum, ans;
int a[40];
//i当前正在选第几个数
//cnt当前选取了几个数
//s当前所选数的和
void dfs(int i,int cnt,int s){if(i==n){if(cnt == k && s==sum){ans++;}return ;}dfs(i+1,cnt ,s);//不选这个数dfs(i+1,cnt+1,s+a[i]);//选这个数}
int main() {// 输入数据cin >> n >> k >> sum;for (int i = 0; i < n; i++) {cin >> a[i];}ans=0;dfs(0,0,0);cout<<ans<<endl;return 0;
}

解法二（错误）：

#include <iostream>
using namespace std;
int n, k, sum, ans;
int a[40];
bool xuan[40];
//s和
//cnt选的个数
void dfs(int s,int cnt){if(s==sum && cnt ==k){ans++;}for(int i=0;i<n;i++){if(!xuan[i]){xuan[i]=1;dfs(s+a[i],cnt+1);xuan[i]=0;}}
}
int main() {// 输入数据cin >> n >> k >> sum;for (int i = 0; i < n; i++) {cin >> a[i];}ans=0;dfs(0,0);cout<<ans<<endl;return 0;
}

这样是错误的，这是因为这样搜索，后方案实际上乘上了-个k!。比如一个组合2,3,5.这样的方法，会把2,3, 5、2,5,3、 3,2,5、 3,5,2、 5,3,2、 5,2,3当成同的方法，之前的搜索方法只会搜到2, 3, 5。

优化

现在我们换一种搜索方法，每次从剩下的数中选取一个数。从1,2,3,… ,30这30个数中选8个数出来，使得和值为200.

如果按上面的代码搜索，根本运行不出来，或者要运行很久。

下面我们经行剪纸

#include <iostream>
using namespace std;
int n, k, sum, ans;
int a[40];
bool xuan[40];
//s表示当前的和
//cnt表示当前选了几个数
//pos表示当前选到了那个数了，下次直接从这个数往后开始
void dfs(int s, int cnt, int pos) {if(s>sum || cnt>k){ //剪枝return ;}if (s == sum && cnt == k) {ans++;}for (int i = pos; i < n; i++) {if (!xuan[i]) {xuan[i] = 1;dfs(s + a[i], cnt + 1, i+1);//i+1从pos后一位开始xuan[i] = 0;}}
}
int main() {n = 30;k = 8;sum = 200;for (int i = 0; i < 30; i++) {a[i] = i + 1;}ans = 0;dfs(0, 0, 0);cout << ans << endl;return 0;
}