递推与递归+DFS

递推与递归+DFS

题目一

1.从1~n 这n个整数中随机选取任意多个，输出所有可能的选择方案

顺序：从1~n依次考虑每个数选 / 不选

#include <bits/stdc++.h>
using namespace std;

int n;
int st[20];
void dfs(int x) {
    if (x > n) {
        for (int i = 1;i <= n;i++) {
            if (st[i] == 1) {
                cout << i << " ";
            }
        }
        cout << endl;
        return;
    }
    // 选
    st[x] = 1;
    dfs(x+1);
    st[x] = 0;

    // 不选
    st[x] = 2;
    dfs(x+1);
    st[x] = 0;
}
int main () {

    cin >> n;
    dfs(1);
    return 0;
}

题目二

#include <bits/stdc++.h>
using namespace std;

int n;
int st[15]; // 表示是否选择
int used[15]; // 存的是答案

void dfs(int x) {
    if (x > n) {
        for (int i = 1;i <= n;i++) {
                cout << used[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 1;i <= n;i++) {
        if (!st[i]){
            st[i] = 1;
            used[x] = i;
            dfs(x+1);
            st[i] = 0;
        }

    }
}
int main () {

    cin >> n;
    dfs(1);
    return 0;
}

题目三

#include <bits/stdc++.h>
using namespace std;


int n,m;
int st[30];
int used[30];

void dfs(int x,int num) {
    if (x > m) {
        for (int i = 1;i <= m;i++) {
            cout << setw(3) << used[i];
        }
        cout << endl;
        return;
    }
    for (int i = num;i <= n;i++) {
        if (!st[i]) {
            st[i] = 1;
            used[x] = i;
            dfs(x+1,i+1);
            st[i] = 0;
        }
    }
}
int main () {

    cin >> n >> m;
    dfs(1,1);
    return 0;
}

题目四

#include <bits/stdc++.h>
using namespace std;


int n,k;
int a[25];
int st[25];
//int sum = 0;
int ans;
int arr[25];
bool judge(int x) {
    for (int i = 2;i*i <= x;i++) {
        if (x%i == 0) return false;
    }
    return true;
}
void dfs(int x,int index) {
    if (x > k) {
        int sum = 0;
        for (int i = 1;i <= k;i++) {
            sum += arr[i];
        }
        if (judge(sum)) ans++;
        return;
    }
    for (int i = index;i <= n;i++) {
        //sum += a[index];
        arr[x] = a[i];
        dfs(x+1,i+1);
        arr[x] = 0;
    }
}
int main () {
    cin >> n >> k;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    dfs(1,1);
    cout << ans;
    return 0;
}