1

I have a question regardng this LeetCode question: 46. Permutations. The following Python solution is very efficient in terms of both runtime and memory usage:

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

        def backtrack(arr, cur):
            if not arr:
                final.append(cur)
                return

            for i in range(len(arr)):
                backtrack(arr[:i] + arr[i+1:], cur + [arr[i]])

        final = list()
        backtrack(nums, list())

        return final

However, in backtrack(arr[:i] + arr[i+1:], cur + [arr[i]]) Python seems to allocate new memory via slicing and concatenation at every level of the recursion. The C++ best practice is different and swaps items in the vector through the backtracking rather than creating a new vector. Is there any optimization Python is doing in the background so that new memory is not allocated at every recursion level? I'm a bit confused here.

Alexey Abramov
  • 435
  • 1
  • 3
  • 16
  • Maybe rather than `arr[i] + arr[i+1]` first pop the element from the array, do backtrack and then insert it to the index i? – null Mar 05 '20 at 16:37

1 Answers1

0

Python's slicing typically copies references to the underlying objects rather than deep copy everything ad hoc. i.e., you are actually just manipulating shallow copies of parts of the list. Because everything is allocated once (as you said, typical implementations in C++ swap the numbers), Python's reference counting and memory management are smart enough to steal ownership of the arr whenever it falls out of scope.

Jason Nguyen
  • 76
  • 6