Permutation Sequence

题目：

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

Example: For n = 3, all permutations are listed as follows:

"123", "132", "213", "231", "312", "321"; If k = 4, the fourth permutation is "231"

分析：

这题目还蛮有意思的，我用了个基础的permutation做，但是似乎可以不建立vector，只记录第k次的结果。

解法：

class Solution {
public:
    /**
      * @param n: n
      * @param k: the kth permutation
      * @return: return the k-th permutation
      */
    void dfs(vector<char> nums, 
            int &count, 
            int k, 
            string instance, 
            vector<string> &permutations) {

        if (count >= k) {
            return;
        }        

        if (instance.size() == nums.size() ) {
            permutations.push_back(instance);
            count++;
            return;
        }

        for (int i = 0; i < nums.size(); i++) {

            if (find(instance.begin(), instance.end(), nums[i]) != instance.end() ) {
                continue;
            }

            instance.push_back(nums[i]);
            dfs(nums, count, k, instance, permutations);
            instance.pop_back();
        }
    }  

    string getPermutation(int n, int k) {
        if (n == 0) {
            string res = "";
            return res;
        }

        vector<string> permutations;
        vector<char> nums;
        for (char i = '1'; i <= '1' + n - 1; i++) {
            nums.push_back(i);
        }

        int count = 0;
        string instance;
        dfs(nums, count, k, instance, permutations);
        return permutations[k - 1];
    }
};