[FIXED] Failing to debug index out of range error in recursive code of Finding Permutation

Issue

This is the leetcode questions on permutation https://leetcode.com/problems/permutations/

Basically, given an array, you have to return all the permutations of it, for instance

I/P:- [1,2,3]

O/P:- [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

This I the recursive code I wrote

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        output = []
        backtrack(nums, [], output)
        return output
    
def backtrack(nums, current, output):
    if(len(nums) == 0):
        output.append(current)
        return
    else:
        for i in range(len(nums)):
            op1 = current
            ip1 = nums
            # Using print statements for debugging purpose
            print(op1)
            print(ip1)
            op1.append(ip1[i])
            ip1.remove(ip1[i])
            backtrack(ip1, op1, output)

This is what I am getting:

basically I getting the first permutation only

This is how my rough recursive tree looks like:

Kindly help me to mitigate this issue!!

This is how I have resolved it:

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        output = []
        backtrack(nums, [], output)
        return output
    
def backtrack(nums, current, output):
    if(len(nums) == 0):
        output.append(current)
        return
    else:
        for i in range(len(nums)):
            ip1 = nums[:i] + nums[i+1:]
            op1 = current + [nums[i]]
            backtrack(ip1, op1, output)

Solution

The main issue is this:

ip1.remove(ip1[i])

While you're iterating over the list, you're also removing elements. As a result, after a few iterations, the number of elements in the list becomes lower than the current value of i and you get the index error.

As a simple workaround, you could maintain the elements in a separate temporary list, where you do the removals.

Answered By - Abhinav Mathur