It helps me to think of backtracking (or recursion in general) as doing a depth first search of an implicit graph. In this problem, the "leaves" of the tree (our solutions) are the permutations of the first n letters. In the higher levels of the tree you have prefix/candidate solutions, beginning with the empty string. You can extend prefix solutions by appending the smallest unused letter to the end and recurring. Here's a picture of the tree for the first example:

This will find the permutations in lexicographical order, as is clear from the picture.