What does array[:] exactly do in this backtracking algorithm, or rather in Python?

Question

So, I was solving(or rather, looking at the solution haha) a question on Leetcode, and this was a solution to allow you to generate all possible permutations of an array with unique integers.

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

        length = len(nums)
        results = []

        def backtrack(first_char_index):
            if first_char_index == length:
                # print(nums == nums[:])
                results.append(nums)

            for index in range(first_char_index, length):
                nums[first_char_index], nums[index] = nums[index], nums[first_char_index]
                backtrack(first_char_index + 1)
                nums[first_char_index], nums[index] = nums[index], nums[first_char_index]

        backtrack(0)
        return results

So, I was testing out the solution, and I realized that this solution only works if inside the if condition inside of the backtrack function, I use results.append(nums[:]) instead of the above results.append(nums).

So I initially figured that this was probably because nums[:] should be used because we need to generate a new copy, but then I had that print statement added before results.append(nums), and found that all of the print statements gave me a True result.

I remember seeing a few solutions with this pattern of having nums[:] instead of nums, and would like to ask if anyone could shed light on what exactly does the extra [:] do? I know that it creates a new copy (i.e different object, but same value), but since it has the same value, why does result in a different result?

To illustrate this, the result with an input of [1, 2, 3] gives

[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]]

when using nums, and

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

(the correct answer), when using nums[:].

Thanks in advance!

EDIT: For some reason, this question is being recognized to be the same as others that are regarding deep/shallow copy. However, I guess what I'm asking here is that since [:] results in a new, different object with the same value, and with the fact that the value of nums and nums[:] is the same (it prints out to be the altered value), shouldn't it be appending an array with the altered value, instead of the original untouched nums array?

``nums == nums[:]`` checks for *value equality*, not *object identity*. Try ``nums is nums[:]`` to check for copies. — MisterMiyagi, Mar 01 '20 at 16:45
Does this answer your question? [Python list slice as shallow copy](https://stackoverflow.com/questions/34231577/python-list-slice-as-shallow-copy) — MisterMiyagi, Mar 01 '20 at 16:49

PMM · Accepted Answer · 2020-03-01T17:11:11.103

3

nums and nums[:] have indeed the same value (that you check using ==), but the are different objects (that you can check using the 'is' keyword). Sequences are mutable, therefore you can change the values they contain without changing the object itself. The [:] simply creates a copy of an existing sequence. This way you have a different object with all the values of the previous one

EDIT: the reason is that, when you append nums to results, nums can still be changed even if it's inside results. Therefore the elements inside results will be changed everytime you change the original nums (in fact in the result all the values are identical). If you create a copy for each element you put in results, instead, the elements will all have different values.

edited Mar 01 '20 at 17:11

answered Mar 01 '20 at 16:37

PMM

366
1
10

1

Yes, i figured this is true from past experiments (i.e that's how i got the fact that it creates a new copy). However, their value is the same, so my question is why the array appended to results is not the same? – Chiah Soon Mar 01 '20 at 16:39
1

Because they are different objects (they therefore have different memory addresses). This way, if you change the copy of nums you won't also change the original copy. If didn't use [:], by changing the copy of nums (ex. appending values) you would also change the original nums. – PMM Mar 01 '20 at 16:41
1

I am still not seeing why the "original values" are being appended to the results array. Sure, i get that nums[:] allow us to not edit the original array, but if the value of nums is the same as nums[:], shouldn't the value of the array appended to the results array be the _altered_ one instead of the _original_ one? – Chiah Soon Mar 01 '20 at 16:49
1

the reason is that, when you append nums to results, nums can still be changed even if it's inside results. Therefore the elements inside results will be changed everytime you change the original nums (in fact in the result all the values are identical). If you create a copy for each element you put in results, instead, the elements will all have different values. – PMM Mar 01 '20 at 17:03
1

Okay, this answers my question! If you'll edit and add this to the answer above I'll mark it as correct :) Thanks! – Chiah Soon Mar 01 '20 at 17:06

What does array[:] exactly do in this backtracking algorithm, or rather in Python?

1 Answers1