Permutation Sequence

Permutation Sequence

 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 kth permutation sequence.

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

------------------- thinking -------------------
there are methods of using array to store left chars or using loop to update the previous inserted chars
http://yucoding.blogspot.com/2013/04/leetcode-question-68-permutation.html
using array to store
https://oj.leetcode.com/discuss/11023/most-concise-c-solution-minimal-memory-required
using updating way to change previous inserted chars
https://oj.leetcode.com/discuss/19357/efficient-solution-without-previous-calculation-factorial

----------------------- using vector to store ---------------
 class Solution {
 public:
     string getPermutation(int n, int k) {
         vector<char> s;
         int factor = 1;
         for (int i = 0; i < n; i++) {
             s.push_back(char('1' + i));
             factor *= i+1;
         }
         string result;
         //bug here, k should be index starting from 0
         k--;
         for (int i = n; i >= 1; i--) {
             factor /= i;
             int ind = k / factor;
             k = k % factor;
             result.push_back(s[ind]);
             s.erase(s.begin()+ind);
         }
         return result;
     }
 };