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

算法思路：

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

算法步骤：

1.对于从1~n的n个整数进行排列，定义一个存储排列的数组a[1...m],一个存储待选数列的数组b[1...n]。

2.从1开始递归，每次选择一个数，即将该数从待选数列中删除，然后将该数存入排列数组a中。

3.如果排列数组a中已经存储了m个数，则输出该排列，同时进行回溯。

4.如果排列数组a中存储的数不足m个，则继续从待选数列中选择下一个数，以此类推。

5.回溯时，将最后一个数从排列数组a中删除，重新将该数存入待选数列b中，然后继续从待选数列中选择下一个数。

6.如果待选数列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)。