This Question can be solved by backtracking? Just math maybe.


  • 0

    This is my backtracking solution and TLE.
    Why it has backtracking tag?

    class Solution {
    public:
        string getPermutation(int n, int k) {
            set<int> st;
            for (int i = 1; i <= n; i++)
                st.insert(i);
            string res;
            int index = 0;
            if (helper(st, k, index, res))
                return res;
            return "";
        }
        bool helper(set<int>& st, int k, int& index, string& s) {
    
            if (st.empty()) {
                index++;
                if (index == k)
                    return true;
                return false;
            }
            
            int n = st.size();
            for (int i = 0; i < n; i++) {
                auto p = st.begin();
                advance(p, i);
                int num = *p;
                st.erase(p);
                s.push_back('0' + num);
                if (helper(st, k, index, s))
                    return true;
                s.pop_back();
                st.insert(num);
            }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.