antivenom's blog

Interesting recursion based question.
By antivenom, 9 years ago, In English

Hi guys,I am practising recursion nowadays and I found this good question based on recursion more of backtracking.I did this question using next_permutation() method.But I find no learning in using a predefined method for this good question(It can teach many good things about recursion)I am really messed up with recursion.can anyone explain me how recursion will do in this question.Thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply