The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,

We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

 

Given n and k, return the k^th permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

DFS从小到大枚举排列，到K时输出。

1 class Solution { 2 private: 3     int a[10]; 4     bool canUse[10]; 5     string ret; 6 public: 7     void dfs(int dep, int maxDep, int &k) 8     { 9         if (k == 0)10             return;11             12         if (dep == maxDep)13         {14             k--;15             if (k == 0)16             {17                 ret = "";18                 for(int i = 0; i < maxDep; i++)19                     ret += (char)(a[i] + '0');20                 return;21             }22         }23         24         for(int i = 1; i <= maxDep; i++)25             if (canUse[i])26             {27                 canUse[i] = false;28                 a[dep] = i;29                 dfs(dep + 1, maxDep, k);30                 canUse[i] = true;31             }32     }33     34     string getPermutation(int n, int k) {35         // Start typing your C/C++ solution below36         // DO NOT write int main() function37         memset(canUse, true, sizeof(canUse));38         39         dfs(0, n, k);40         41         return ret;42     }43 };