这是一道有关递归的题

Question

这一套是每日一练的困难部分，我的境界不够，但是还是想了解一下。我对本题并没有思路。

Answer 1

n个数的排列组合问题递归思路如下：
定义一个静态数组a，a中元素从1到n排列。每一轮递归都会用到这个数组。
先计算s =(n-1)!，然后计算 k / s，得到的这个数，就是本轮递归result[0]的第一个数，然后把这个数移动到数组的最后，后续的序列就不能再使用这个数字。
然后判断 k%s是否为0，如果为0，说明本次最后的一个序列就是要求的，并且这个需求是剩余数中的最大数，逆序从数组a中组合就可以了。
如果不为0，就递归 n-1 时的情况，这时，需要减去已经跳过的序列个数。
特别的，当k=1的时候，直接用数组a的前n个数拼起来就是要求的。

运行结果：

代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* getPermutation(int n, int k)
{
    int s1 = 1, i, j, t;
    char* result = (char*)malloc(n + 1);
    static int a[9] = { 1,2,3,4,5,6,7,8,9 };
    char* tmp = 0;
    int bs;
    result[n] = '\0';


    if (k == 1)
    {
        for (i = 0; i < n; i++)
            result[i] = a[i] + '0';
        return result;
    }

    //计算n-1的阶乘
    for (i = 1; i <= n - 1; i++)
        s1 *= i;


    if (k == n * s1) //k就是n的阶乘
    {
        for (i = 0; i < n; i++)
        {
            result[i] = a[n - 1 - i]+'0';
        }
        return result;
    }


    bs = k / s1;

    result[0] = a[bs] + '0'; //第一个数字


    if (k % s1 == 0)
    {
        for (i = 1; i < n; i++)
            result[i] = a[n - i] + '0';
        return result;
    }
    else
    {
        //将a[bs]从数组中移除
        for (i = 0; i < 9; i++)
        {
            if (a[i] == a[bs])
            {
                t = a[bs];
                for (j = i; j < 8; j++)
                    a[j] = a[j + 1];
                a[8] = t;
            }
        }
        tmp = getPermutation(n - 1, k % s1);
        strcpy(result + 1, tmp);
        free(tmp);
        return result;
    }
}
int main()
{
    int n, k;
    char* p = 0;
    scanf("%d %d", &n, &k);
    p = getPermutation(n, k);
    if (p)
    {
        printf("%s", p);
        free(p);
    }
    return 0;
}