Блог пользователя antivenom

Interesting recursion based question.
Автор antivenom, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить