I came across this algorithm in a book, and have been struggling to understand the basic idea. The books says it uses backtracking to print all possible permutations of the characters in a string. In Python, the algorithm is given as:def bitStr(n, s):    if n == 1: return s    return [digit + bits for digit in bitStr(1, s) for bits in bitStr(n - 1, s)]print(bitStr(3, 'abc'))I'm pretty weak in algorithmic thinking and am struggling for both an intuitive understanding of this, as well as tracing it. Can somebody explain what this algorithm does and how exactly is uses 'backtracking'?
Using backtracking to find all possible permutations in a string
algorithms;permutations;backtracking
Backtracking is a general algorithm that incrementally builds candidates to the solutions, and abandons each partial candidate (backtracks) as soon as it determines that the candidate (Wikipedia).So, basically, what you do is build incrementally all permutations. As soon as as you build a single permutation, you backtrack and build another one, and so on until you generate all $n!$ possible permutations, say, on $n$ symbols.Example: $n=3$, $S=\{1,2,3\}$.You start with $1$. Then you move forward an choose $2$ (since $1$ has already been chosen), and then you choose $3$. At that point you have built the first permutation $123$. Then you backtrack and select $3$ instead of $2$, then select $2$, and you have $132$. You backtrack again, but you have already used $2$ and $3$, so you backtrack again (one level up where), and choose $2$ instead of $1$, then you select $1$, and finally $3$, so you have $213$.The following picture should clarify the basic idea:In other words, you simply traverse the tree, and when you reach the leaf you print the permutation. Then you backtrack one level up, and try another option. Moving one level up the tree is what we call the backtracking in this case.As for implementation, the backtracking is usually implemented using recursive call(s) as in your example. I assume that you have necessary programming skills to implement this basic idea yourself, in particular solving problems using recursive calls. 