WA一个点

Lyd1107 @ 2025-01-11 14:34:05

#include <bits/stdc++.h>
using namespace std;
#define itn int
int n, k;
int a[15];
int u[15];

void dfs(int k) {
    if (k  == n + 1) {
        for (int i = 1; i < k; i++) {
            cout << a[i] << " ";
        }
        cout << '\n';
        return;
    }
    for (itn i = 1; i <= n ; i++) {
        if (!u[i]) {
            u[i] = 1;
            a[k] = i;
            dfs(k + 1);
            u[i] = 0;
        }

    }
}

signed main() {
    cin >> n >> k;
    dfs(1);
    return 0;
}

by chenyiyang0609 @ 2025-01-12 17:01:42

Code

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

int n, k;  // 定义两个整型变量，n表示学生的总人数，k表示要从中选出的人数
int a[15];    // 定义数组a，用于存储一种排列的情况，这里数组大小设为15，可根据实际情况调整，只要能满足题目中n的最大范围即可
bool vis[15]; // 定义布尔类型数组vis，用于标记每个数字（对应学生编号）是否已经被选入当前排列中，初始化为false，表示都未被选

// dfs函数用于通过深度优先搜索来生成所有满足要求的排列情况
// 参数u表示当前正在考虑选择的学生编号（从1到n进行遍历选择），cur表示当前已经选入排列中的学生个数
void dfs(int u, int cur) { 
    // 当已经选入排列中的学生个数等于要求选出的人数k时，说明已经得到了一种满足要求的排列
    if (cur == k) {  
        // 循环遍历当前已经选好的k个数，也就是数组a的前k个元素，将其按格式输出
        for (int i = 0; i < k; i++) {
            printf("%d ", a[i]);
        }
        puts("");  // 输出一个换行符，使每种排列占一行，符合输出格式要求
        return;    // 结束当前递归分支，回溯去寻找下一种排列情况
    }
    // 如果当前考虑的学生编号u已经超过了总人数n，说明已经无法再选出更多的学生来构成排列了，直接返回
    if (u > n) return;  

    // 从1到n遍历所有学生编号，尝试选择合适的学生放入当前排列中
    for (int i = 1; i <= n; i++) {
        // 如果当前编号为i的学生还没有被选入当前排列（vis[i]为false表示未被选）
        if (!vis[i]) {
            // 将该学生标记为已选，即把vis[i]设为true
            vis[i] = true;
            // 将编号为i的学生放入当前排列的cur位置，也就是数组a的cur下标处
            a[cur] = i;
            // 递归调用dfs函数，继续考虑下一个学生编号（u + 1），同时已选学生个数加1（cur + 1）
            dfs(u + 1, cur + 1);
            // 当从当前这个选择情况的递归分支返回后（也就是已经探索完以这个选择为开头的所有排列情况后），
            // 需要把该学生的已选标记清除，这样后续其他排列情况的生成过程中还可以再次选择这个学生
            vis[i] = false;
        }
    }
}

int main() {
    // 从标准输入读取学生总人数n和要选出的人数k
    cin >> n >> k;
    // 调用dfs函数开始进行深度优先搜索，初始从第一个学生编号（u = 1）开始考虑，且当前已选学生个数为0（cur = 0）
    dfs(1, 0);
    return 0;
}