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

• ``````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'.

• 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.

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