The first idea when I see this problem is backtracking to enumerate all possible permutations and pick up the kth one.

1:  class Solution {  
2:  private:  
3:    int kth;  
4:    string res;  
5:  public:  
6:    string getPermutation(int n, int k) {  
7:      string s, sol;  
8:      kth = k;  
9:      for (int i = 1; i <= n; i++) {  
10:        s += '0' + i;  
11:      }  
12:      helper(s, sol);  
13:      return res;  
14:    }  
15:    void helper(string s, string sol) {  
16:      if (s.empty()) {  
17:        kth--;  
18:        return;  
19:      }  
20:      for (int i = 0; i < s.size(); i++) {  
21:        char c = s[i];  
22:        sol += c;  
23:        s.erase(s.begin()+i);  
24:        helper(s, sol);  
25:        if (kth == 0 && res.empty()) {  
26:          res = sol;  
27:          return;  
28:        }  
29:        sol.pop_back();  
30:        s.insert(s.begin()+i, c);  
31:      }  
32:      return;  
33:    }  
34:  };  

However, I got TLE. Obviously, in order to get the sequence that problem states, the code seems to be very efficient because there is many erase and insert operation on string.

Another way is math. We know that for set [1,2,...,n], we have n! in total permutations. To get the kth permutation, we compute from the first position. So for first position, we have n * (n-1)! permutations. Thus, the first number for kth permutation should be k / (n-1)!. After fixing the first number in permutation, we have k2 = k % (n-1)! permutations left. So we'll compute the second number as k2 / (n-2)!.  We'll continue computing until we find all n numbers for kth permutation.

1:  class Solution {  
2:  public:  
3:    string getPermutation(int n, int k) {  
4:      string nums;  
5:      int permCount = 1;  
6:      string res;  
7:      for (int i = 1; i <= n; i++) {  
8:        nums += '0' + i;  
9:        permCount *= i;  
10:      }  
11:      k--; // this is to adjust the index.  
12:      for (int i = 0; i < n; i++) {  
13:        permCount /= n-i;  
14:        int index = k / permCount;  
15:        res += nums[index];  
16:        nums.erase(nums.begin()+index);  
17:        k %= permCount;  
18:      }  
19:      return res;  
20:    }  
21:  };