Understanding the for loop in Python permutation algorithm (Back-Tracking)

Question

I'm currently working on a permutation algorithm in Python, and I'm having trouble understanding how the for loop inside the backtrack function works. I would appreciate it if someone could provide a clear explanation of its behaviour.

Here's the code I'm referring to:

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        res = []

        def backtrack(path, visited):
            if len(path) == len(nums):
                res.append(path)
                return

            for i in range(len(nums)):
                print(i)
                print(path)
                print(visited)
                if not visited[i]:
                    visited[i] = True
                    backtrack(path + [nums[i]], visited)
                    visited[i] = False

        backtrack([], [False] * len(nums))
        return res

print(Solution().permute(nums=[1, 2, 3]))

Specifically, I would like to understand the following points:

1. How does the range(len(nums)) expression in the for statement determine the iteration over the nums list?

2. What does the if not visited[i] condition inside the loop do?

3. How does the backtrack(path + [nums[i]], visited) line contribute to the permutation generation?

However, during my debugging attempts, I noticed that the program successfully iterates up to i = 2, but it fails to backtrack and continue with i = 1. As a result, it terminates prematurely without generating all the possible permutations.

I've verified that the input list nums is correct and the base case for the termination condition (len(path) == len(nums)) is working as expected. I suspect that the issue lies in how the backtracking mechanism is implemented.

Could someone please help me understand why the program is not backtracking to the previous iteration in the for loop? Is there a problem with the backtracking logic or any potential mistakes I might have made in the code?

Thank you for your time and assistance!

---

Any clarification or step-by-step explanation of the loop's execution would be greatly appreciated. Thank you in advance!

Feel free to modify or add more specific details to the question based on your needs and provide any additional information or context that might be helpful for others to understand and answer your question effectively

Answer 1

Your code runs perfectly fine.

It does the standard recursive-backtracking thing: it uses recursion to emulate k nested loops, and collects the results generated at the deepest innermost loop, following the shrinking domain paradigm, as if in the pseudocode

permute(nums) =

    let k = length nums

    for (n1, rest1) picked_from nums:
      for (n2, rest2) picked_from rest1:
        for (n3, rest3) picked_from rest2:
           ............
              for (nk, _) picked_from rest_k1: # rest_k1=[nk]
                   yield [n1,n2,n3, ..., nk]

The pseudocode for (n,rest) picked_from nums here means that n is a number picked from nums, one after another, and for each choice of which n to pick, rest is what's left of nums. In other words, nums = [...a, n, ...b] and rest = [...a, ...b], for each choice of a and b.

For your test example of permute([1,2,3]), the top loop level is

     for (n1,rest1) in [ (1,[2,3]), (2,[1,3]), (3,[1,2]) ]:
       ....

so overall it runs as

      (n1,rest1) = (1,[2,3])
          (n2,rest2) = (2,[3])
               (n3,_) = (3,[])
                   yield [1,2,3]
                   ; endloop
          (n2,rest2) = (3,[2])
               (n3,_) = (2,[])
                   yield [1,3,2]
                   ; endloop
               ; endloop
      (n1,rest1) = (2,[1,3])
          (n2,rest2) = (1,[3])
               (n3,_) = (3,[])
                   yield [2,1,3]
                   ; endloop
          (n2,rest2) = (3,[1])
      .....

Each loop maintains its own set of loop variables, and when the inner loop runs its course, the control returns back into the loop one level above, and that loop continues with its next choice,

That return into the upper loop is what is referred to as "backtracking".

We can't write out k nested loops at run time of course, since we don't know the k value until the program runs.

But the recursion on i from 0 to k-1 where k = len(nums) creates the computational structure of k nested invocations of our recursive function, at run-time, which act as if they were the k nested loops. Each invocation maintains its own set of variables just as the for loop would. When a recursive call returns, the control returns back to that invocation which had made the call, and having full access to its own state it is able to make the next "guess".

The picking of a number and getting the rest of the nums is emulated with

            for i in range(len(nums)):
                if not visited[i]:
                    visited[i] = True
                    backtrack(path + [nums[i]], visited)
                    visited[i] = False

by setting the visited[i] to True while picking the nums[i] number and recording it in the value path which will be the eventual next piece of output, at the kth level, when it is added into the overall result:

            if len(path) == len(nums):  
                res.append(path)        
                return

The if condition holds only at the deepest level. There i==k, all the numbers from nums have been picked and placed into path (by the path + [nums[i]] expressions, on the way into the deepest recursion level) so that now len(path)==len(nums) holds, and the choices made are recorded into the overall output res with res.append(path). No more recursive calls are made -- we immediately return, which is what makes it the deepest level invocation.

There's no need to undo the appending of the nums[i] to path, since when the recursive call to backtrack returns, the invocation which called it holds on to its own copy of path which hasn't been changed -- the extended value was passed to that recursive call as an argument.

The picking of i, being recorded in a global -- to the recursions -- variable visited with visited[i]=True, must be undone (with visited[i]=False) before making the next choice i+1, so that the recursive invocation is able to pick the ith element of nums for its choice.

---

In your function every guess is eventually accepted, but in the general recursive-backtracking scheme of things some guesses/choices might well get rejected, possibly cutting the enumeration short if it is already known to not have any chance succeeding. Thus in the end only the successful choices are recorded in the output sequence.

As an aside, the variable names in your code are not really helpful. visited could be better named used, path could be picked or something, and backtrack -- just solve in general or, here e.g. generate_permutations. Yes the backtracking technique is used but that's not the essence of what the function is doing.

The essence of the function is the nature of its result, not the technique that is used to get it.