issue with permute_recursive

[DonMiller9294]

What would you like to share?

Your code looks mostly correct, but there's one issue in the permute_recursive function due to the modification of the nums list. Lists in Python are mutable, and when you use nums.pop(0), it modifies the original nums list. This can lead to incorrect results and even an infinite loop.

To fix this, you should pass a copy of the nums list to the recursive function. Here's the corrected permute_recursive function:

def permute_recursive(nums: list[int]) -> list[list[int]]:
"""
Return all permutations.

>>> permute_recursive([1, 2, 3])
[[3, 2, 1], [2, 3, 1], [1, 3, 2], [3, 1, 2], [2, 1, 3], [1, 2, 3]]
"""
result: list[list[int]] = []
if len(nums) == 0:
    return [[]]
for _ in range(len(nums)):
    n = nums.pop(0)
    permutations = permute_recursive(nums[:])  # Make a copy of nums
    for perm in permutations:
        perm.append(n)
    result.extend(permutations)
    nums.append(n)
return result

With this modification, your code should work correctly for both `permute_recursive` and `permute_backtrack`.

### Additional information

_No response_

[Ayushrai001]

def generate_permutations(nums):
def backtrack(start):
if start == len(nums):
result.append(nums[:])
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start] # Swap elements
backtrack(start + 1)

Recurse

        nums[start], nums[i] = nums[i], nums[start]  # Backtrack
        
result = []
backtrack(0)
return result

Example usage

input_nums = [1, 2, 3]
permutations = generate_permutations(input_nums)
print(permutations)

[tianyizheng02]

I think it's more readable to make the list copy using nums.copy(). Feel free to open a PR to make this fix.

[aryan1165]

Hey. I have added a PR #9115 fixing this issue. As you mentioned, I have used nums.copy() to pass a copy of the nums list. Please review it. Thanks.