选择整数1至n中m个数进行按照字典顺序排列C语言

以下是C语言代码实现：

#include <stdio.h>

int n, m;
int a[100], vis[100];

void dfs(int step)
{
    if (step > m) {
        for (int i = 1; i <= m; i++)
            printf("%d ", a[i]);
        printf("\n");
        return;
    }
    for (int i = (step == 1 ? 1 : a[step-1]+1); i <= n; i++) {
        if (!vis[i]) {
            vis[i] = 1;
            a[step] = i;
            dfs(step + 1);
            vis[i] = 0;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    dfs(1);
    return 0;
}

与上一个问题的代码相比，主要修改了第二个for循环的起始值。如果当前是第一个数，则从1开始遍历，否则从上一个数的后一个数开始遍历，避免了重复输出。

相关问题

选择整数1至n中m个数进行字典序全排列C语言

以下是C语言代码实现：

#include <stdio.h>

int n, m;
int a[100], vis[100];

void dfs(int step)
{
    if (step > m) {
        for (int i = 1; i <= m; i++)
            printf("%d ", a[i]);
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            vis[i] = 1;
            a[step] = i;
            dfs(step + 1);
            vis[i] = 0;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    dfs(1);
    return 0;
}

其中，`n`表示1至n中的数，`m`表示选出的数的个数，`a`数组记录当前排列，`vis`数组记录数字是否已经被选过。通过深度优先搜索遍历所有排列，按照字典序输出。

选择整数1至n中m个数进行字典序全排列。

题目描述：从1到n中选择m个整数进行字典序全排列。

解题思路：这是一道典型的回溯算法题目。我们可以使用递归的方式来实现。首先，我们需要定义一个数组来存储已经选择的数字，以及一个布尔数组来标记数字是否已经被选择。然后，我们从1到n中依次选择数字，如果该数字没有被选择过，我们就将其加入已选择的数组中，并将其标记为已选择。然后，我们递归调用函数，继续选择下一个数字。当已选择的数字个数达到m时，我们就可以输出当前的排列。最后，我们需要将已选择的数字从数组中删除，并将其标记为未选择，以便下一次选择。

代码实现：

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 10;

int n, m;
int path[N];
bool st[N];

void dfs(int u)
{
    if (u == m)
    {
        for (int i = ; i < m; i ++ ) cout << path[i] << ' ';
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; i ++ )
        if (!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }
}

int main()
{
    cin >> n >> m;

    dfs();

    return ;
}

时间复杂度：O(n^m)。