Debug this backtrack algorithm for Leetcode 46: Permulation problrm?

Question

I'm using the backtracking algorithm to solve the classical. Leetcode permutation problem.

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

It's pretty straightforward, and I can solve it using the following code:

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        solutions = []
        def backtrack(state):
            # print(state)
            # print(remain)
            if len(state) == len(nums):
                solutions.append(state.copy())
                # return

            for n in nums:
                if n not in set(state):
                    state.append(n)
                    backtrack(state)
                    state.pop()

        state = []
        backtrack(state)
        return solutions

However, when I try to also pass the index of the unselected element (named remain), see the following:

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        solutions = []
        def backtrack(state, remain):
            if len(state) == len(nums):
                solutions.append(state.copy())
                # return

            for i in remain:
                state.append(nums[i])
                remain.remove(i)
                backtrack(state, remain)
                state.pop()
                remain.add(i)

        full_ind = set([i for i in range(len(nums))])
        state = []
        backtrack(state, full_ind)
        return solutions

This doesn't work, and I always get redundancy in my solutions. See below: enter image description here I think there must be some stupid mistake I made, but I can't figure it out. Could anyone help me with this? I struggled a lot to understand what happened. Really Appreciate it :) !!

Answer 1

As a comment said, you are modifying a list while iterating over it.

Your second snippet works when you change the loop to:

for i in list(remain):

Passing remain to the list constructor creates a list from the original set which you can iterate over while modifying the set.