首页 算法题库

# dfs1

给定 n 个整数，要求选出 K 个数，使得选出来的 K 个数的和为 sum; 求一下有多少种情况；

#include <iostream>
using namespace std;
//n 代表一共多少个数，k 代表需要选的的数个数，sum 代表当前累加的数，ans 表示有多少种情况
int n, k, sum, ans;
int a[40];
//cnt 当前累加的个数； s = 当前累加的数之和
void dfs(int i, int cnt, int s) {
	if (i == n) {
		if (cnt == k && s == sum) {
			ans++;
		}
	}
	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];
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);
    return 0; 
}
第二种会显示 12，因为组合 2，3，5 和 3，2，5 和 5，3，2 等当成了不同方法。等待优化
从 0 到 29 这 30 个数中选出 8 个数，使其和值为 200；
#include<iostream>
using namespace std;
int n, k, sum, ans;
int a[40];
void dfs(int i, int cnt, int s) {
	if (cnt > k) {
		return;
	}if (s > sum) {
		return;
	}
	if (i == n && cnt == k && s == sum) {
	ans++;
	}
	dfs(i + 1, cnt,s);
	dfs(i + 1, cnt+1,s + a[i]);
}
int main() {
	n = 30;
	k = 8;
	sum = 200;
	for (int i = 0; i < 30; i++) {
		a[i] = a[i] + 1;
	}
	ans = 0;
	dfs(0, 0, 0);
	cout << ans << endl;
	return 0;
}
# dfs2
输入整数 n, 表示木棍数量 (3 < n <= 10)，接下来输入 n 根木棍的长度 pi (1 < pi < 10000), 看是否能装出等边三角形。
#include <iostream>
using namespace std;
int p[15];
bool vis[15];
int n,sum = 0;
bool f;
void dfs(int cnt, int s, int st){
    if(f){
        return;
    }
    if(cnt == 3){
        f == true;
        return;
    }
    if(sum = sum/3){
        dfs(cnt+1,0,0);
        return;
    }
    for(int i = 0;i < n; i++){
        if(!vis[i]){
            vis[i] = true;
            dfs(p,s+p[i],i+1);
            vis[i] = false
        }
    }
}
int main(){
  
    scanf("%d",&n);
    
    for(int i = 0; i < n; i++{
        scanf("%d",&p[i]);
        sum += p[i];
    }
    if(sum % 3 != 0) cout << "nono" << endl;
    else{
        dfs(0,0,0);
        if(f){
             cout << "yesyes";
        }
        else{
            cout << "nono"; 
        }
    }
    return 0;
}
memset(dp,0,sizeof(dp))

 更新于