67分求调（第二个测试点WA）

DougNo1 @ 2024-09-08 16:43:22

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,k,sum=0;
    int a[20];
    cin>>n>>k;
    if(k==1){
        for(int i=1;i<=n;i++) cout<<i<<endl;
        return 0;
    }
    for(int i=0;i<n;i++){
        a[i]=i+1;
        if(i<k) cout<<a[i]<<" ";
    } 
    cout<<endl;
    sum++;
    while(next_permutation(a,a+n)){
        for(int i=0;i<k;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
        sum++;
    }
    return 0;
}

by CD_Sun_doer @ 2024-09-11 21:10:03

这个题用 next_permutation 反而不好用，随便举个例子输入 10 3 有好多重复的，你自己手搓一下，其实要想过要加个哈希啥的去重，不如用dfs

by chenyiyang0609 @ 2025-01-12 17:05:57

dfs是个好东西你可以用用dfs 如果你没有读题，传送门。 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;
}