Difference between pop and [:-1] for lists, and different behaviour for s[:-1] when s is a string or a list

I’ve been practicing on leetcode recently and have just done the question "Combination Sum" (abridged, the full statement can be found at https://leetcode.com/problems/combination-sum/).

Given an array of distinct integers candidates and a target integer
target, return a list of all unique combinations of candidates where
the chosen numbers sum to target. You may return the combinations in
any order.

The same number may be chosen from candidates an unlimited number of
times. Two combinations are unique if the frequency of at least one of
the chosen numbers is different.

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

I solved the problem correctly using a simple backtracking method which builds up a solution partial and then appends it to an array ans using the following helper function (partial is a list)

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        def helper(candidates, target, partial):
            if target == 0:
                ans.append(partial[:])
                return
            if target < 0:
                return
            for i in range(0,len(candidates)):
                partial.append(candidates[i])
                helper(candidates[i:], target-candidates[i], partial)
                partial.pop()
        
        candidates.sort()
        helper(candidates,target,[])
        return ans

This code works and I’m happy with it. However, if I change the final line to:

partial = partial[:-1]

The solution no longer works. In particular, elements don’t get removed as I would like, and my ans array ends up getting solutions with huge numbers of elements which are incorrect. Intuitively I expected these to serve the same purpose of removing the last element from partial.

I suspect it has something to do with references and list slicing that I’m missing. Why didn’t I have this problem when I solved the leetcode problem combinations of a phone number (see https://leetcode.com/problems/letter-combinations-of-a-phone-number/) which asks to enumerate all possible strings that come from a digit-letter phone mapping, given a string of digits?

Here I used the same helper function structure:

def letterCombinations(self, digits: str) -> List[str]:
        ans = []
        MAPPING = ('0', '1', "abc", "def", 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz')
        def helper(s, partial_sol):
            if len(s) == 0:
                ans.append(partial_sol)
                return
            else:
                for i in MAPPING[int(s[0])]:
                    partial_sol = partial_sol + i
                    helper(s[1:], partial_sol)
                    partial_sol = partial_sol[:-1]
        if len(digits) == 0:
            return ans
        helper(digits, "")
        return(ans)

and my solution was correct. Note though that I have used the [:-1] method which didn’t work with the first problem on lists, but is with this problem on strings. So I can see that whatever is going on is different for strings versus lists (as in the phone number problem, partial is a string rather than a list), I just don’t know exactly what it is, or why.

In short, my questions are:

1. Why does my solution for Combination Sum not work when I change from popping partial to:

partial = partial[:-1]

2. Why does that solution not work for Combination Sum (which uses lists) but it does for Letters from a Phone Number (which uses strings)?

>Solution :

You’re correct it has to do with references and list slicing.

partial.pop() modifies the list bound to partial in-place.

partial = partial[:-1] makes a shallow copy of the list, and rebinds partial to the new list.

This is an important distinction because rebinding doesn’t change any other aliases referring to the original list, which includes the caller’s binding to that same list. To make the two behave almost equivalently (pop is much more efficient, and unlike slicing, will error on an empty list) you can use:

partial[:] = partial[:-1]

which reassigns the contents of the original list to the contents of the shallow copy, or, with equivalent (possibly slightly better) performance than pop:

# Errors on empty list like pop
del partial[-1]

# Or to silently do nothing when applied to an empty list:
del partial[-1:]

which directly deletes the element without returning it.

None of these can be made to work with str, because str is immutable; it’s impossible to modify aliases of the same str in place, you can only make new str and rebind a given name, which doesn’t work for this case. An easy solution is to make your code that works with str convert it to either a list, or, if only ASCII/latin-1 characters occur in the str to encode it to bytes and then convert to bytearray, which is mutable and might allow you to use your code that expects mutable sequences more directly.