这道题用DFS加计数肯定是可以做的，但是我忽然想不起下一个排列的非递归做法了。后来在网上找到如下：

如何计算字符串的下一个排列了？来考虑"926520"这个字符串，我们从后向前找第一双相邻的递增数字，"20"、"52"都是非递增的，"26 "即满足要求，称前一个数字2为替换数，替换数的下标称为替换点，再从后面找一个比替换数大的最小数（这个数必然存在），0、2都不行，5可以，将5和2交换得到"956220"，然后再将替换点后的字符串"6220"颠倒即得到"950226"。

回到这道题目，显然有数学方法可以做的。其实就是计算n位时，先算出后面的数的排列的数量(n-1)!，然后除一下，就能得到n在剩余的排列里的位置了。

假设集合为[1,2,3,4]，求出第6个组合。

第6个组合对应的下标为5（下标从0开始），我们首先求出5所对应的lehmer码：

5/3! = 0 余5

5/2! = 2 余1

1/1! = 1 余0

0 (lehmer code最后一位总为0)

所以所求lehmer码为0210

当前集合对应的序列为1234

接下来将lehmer码中的每个数字当做当前序列的下标，下标0对应的集合元素为1，当前序列变成234；下标2对应的集合元素为4，当前序列变成23；下标1对应的集合元素为3，当前序列变成2；下标0对应的元素为2

所以所求的组合即为1432

实现上要注意的是：1. lehmer码最后一位总是0；2. k也是从0开始，所以要k--；

import java.util.*;public class Solution {    public String getPermutation(int n, int k) {        k--; // start from index 0        ArrayList
     
       arr = new ArrayList
      
       ();        ArrayList
       
         pos = new ArrayList
        
         ();        for (int i = 1; i <= n; i++)        {            arr.add(i);        }        int factor = 1;        for (int i = 1; i < n; i++)        {            factor *= i;        }        for (int i = n-1; i >= 1; i--)        {            pos.add(k / factor);            k = k % factor;            factor /= i;        }        pos.add(0);        StringBuilder sb = new StringBuilder();        for (int i = 0; i < pos.size(); i++)        {            int p = pos.get(i);            sb.append(arr.get(p));            arr.remove(p);        }        return sb.toString();    }}
        
       
      
     

第二遍：

其实这道题是将(K-1，因为从1开始)分解成A*(n-1)!+B*(n-2)!+...+X*(1)!，然后A,B,C,...都是在剩余数组的位置。这样的话，就可以通过辗转除法得到这些系数，然后在剩余的数组中去得到该元素，加到字符串后面。Annie的解法更直观：https://github.com/AnnieKim/LeetCode/blob/master/PermutationSequence.h

class Solution {public:    string getPermutation(int n, int k) {        int factorial = 1;        for (int i = 1; i <= n; i++)        {            factorial *= i;        }                string result;        result.resize(n);        for (int i = 0; i < n; i++)        {            result[i] = i + '1';        }                k--;        for (int i = 0; i < n; i++)        {            factorial /= (n - i);            int idx = k / factorial;            for (int j = i + idx; j < n && j > i; j--)            {                swap(result[j], result[j-1]);            }            k %= factorial;        }        return result;    }};