[C++ backtracking] Concise code with explanation and examples


  • 0
    H
    class Solution {
    public:
        void find (vector<int> &candidates, int permutation, int ith, string &res) {
            if (candidates.empty()) return;
            
            permutation /= candidates.size();
            int num_idx = ith / permutation;
            res += to_string(candidates[num_idx]);
            candidates.erase(candidates.begin() + num_idx);
            find (candidates, permutation, ith % permutation, res);
        }
    
        string getPermutation(int n, int k) {
            int permutation = 1;
            for (int i = 2; i <= n; ++i) permutation *= i;
            
            vector<int> num(n, 0);
            for (int i = 0; i < n; ++i) num[i] = i + 1;
            
            string res;
            find (num, permutation, k - 1, res);
            return res;
        }
    };
    
    • The backtracking function is to solve this problem: Given number set A of size n ({1, 3, 8, ...}, it's not necessary to be continue numbers, but need to be sorted) and want to find the kth permutation of this set.
      1.1 The base case is, A is empty and k is 0. The result is an empty string.
      1.2 When A is {a} and k is 0, the result is "a".
      1.3 When A is {a, b} and k can be either 0 or 1, from here we start backtracking...

    • For example, when A is {1, 3, 8, 9}, all permutation is:
      "1 + all permutation of {3, 8, 9} (1389, 1398, 1893 ...)"
      "3 + all permutation of {1, 8, 9}"
      ...
      And we know, all permutation of {3, 8, 9} is of size 6, so the first 6 permutations (k = 0, 1, 2, .. 5) must start with "1". Similarly, permutations start with "3" is the 7th permutation to 12th permutation (k = 6, 7, 8, .. 11) and so on.

    • When k = 10, we know the result string must start with "3". But we'll need to determine the last 3 digits. Because all permutations start with "1" is of size 6, so the last three digits is (10 - 6)th permutation of set {1, 8, 9}.

    • So we're given a ordered set A of size n, we want to find the kth permutation S of this set. First, the number of permutations for set of size (n - 1) is p. Then, we know the first digit of S is the (k / p)th element in A, and we remove this element from A and get the set A'. From here, we know the last (n - 1) digits are the (k % p)th permutation in A'.


  • 0

    backtracking means back and tracking. I do not think your code might run back.
    Your recursive solution is good but not backtracking.
    I personally think this problem is not backtracking probblem.


Log in to reply
 

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