C语言实现1~n中选取m个元素的排列算法：递归回溯法详解

本文将使用递归回溯法设计一个算法，求从1~n 的n 个整数中取出 m 个元素的排列，要求每个元素最多只能取一次，并用C语言写出代码，同时给出文字的算法说明，计算时间复杂度和分析空间复杂度。

算法思路

采用递归回溯法，从1开始递归，每次选择一个数，即将该数从待选数列中删除，然后继续从待选数列中选择下一个数，直到选完m个数为止，将这m个数输出，然后回溯到上一级，再从待选数列中选择下一个数，以此类推，直到所有情况都遍历完为止。

算法步骤

对于从1~n的n个整数进行排列，定义一个存储排列的数组a[1...m]，一个存储待选数列的数组b[1...n]。
从1开始递归，每次选择一个数，即将该数从待选数列中删除，然后将该数存入排列数组a中。
如果排列数组a中已经存储了m个数，则输出该排列，同时进行回溯。
如果排列数组a中存储的数不足m个，则继续从待选数列中选择下一个数，以此类推。
回溯时，将最后一个数从排列数组a中删除，重新将该数存入待选数列b中，然后继续从待选数列中选择下一个数。
如果待选数列b为空，即所有情况都遍历完了，结束递归。

算法代码

#include <stdio.h>

#define MAXN 100
#define MAXM 10

int a[MAXM], b[MAXN];
int n, m;

void perm(int k)
{
    if (k == m) {
        for (int i = 0; i < m; i++)
            printf('%d ', a[i]);
        printf('\n');
        return;
    }
    for (int i = 0; i < n; i++)
        if (b[i] != -1) {
            a[k] = b[i];
            int tmp = b[i];
            b[i] = -1;
            perm(k + 1);
            b[i] = tmp;
        }
}

int main()
{
    scanf('%d%d', &n, &m);
    for (int i = 0; i < n; i++)
        b[i] = i + 1;
    perm(0);
    return 0;
}

算法时间复杂度

对于每个待选数，都有两种选择：选择该数或不选择该数。因此，总共有n个待选数，每个待选数有两种选择，所以时间复杂度为O(2^n)。

算法空间复杂度

递归深度为m，每次递归需要存储排列数组a和待选数列b，因此空间复杂度为O(m+n)。