LeetCode #494: Target Sum (Python) Below is my solution to LC #494: Target Sum (given a list of numbers and a target integer, find out how many different ways the numbers can be subtracted from the total sum to result in the target sum).

There's one very common pattern in Python here that I question, and it's the use of for num in nums[1:]:. Iterating over nums[1:] is very explicit and readable, but it results in the creation of a whole new array when that really isn't our intention. That also means additional wasted time and wasted memory.

I used to always do for i in range(1, len(nums)): in these situations, but I see most other people using nums[1:]. Would love to hear thoughts on that.

And if there's a cleaner way to write this without having to initialize the counts hash from nums[0] separately from the body of the loop, that'd be great too. I couldn't think of a cleaner way.

class Solution:

    def findTargetSumWays(self, nums: List[int], S: int) -&gt; int:
        counts = {nums[0]: 1, -nums[0]: 1}
        if nums[0] == 0:
            counts[0] += 1
        for num in nums[1:]:
            keys = list(counts)
            new = {}
            for key in keys:
                if key + num not in new:
                    new[key + num] = 0
                if key - num not in new:
                    new[key - num] = 0
                new[key + num] += counts[key]
                new[key - num] += counts[key]
            counts = new
        return counts[S] if S in counts else 0
```
for num in nums[1:] is the prefered way to iterate over a partition of an array; if you are worried about performance, it actually is faster, because accessing by index is more expensive in python than copying then iterating values (you can play with snippets of timeit to verify that claim, but I'm fairly sure of that - accessing by index in python involves way more checks and operations than it does in a language like C).

The performance issue with your program, if there is one, isn't there. The copy is just done once in the outter loop, and since it is repeated by num your inner loop is way more costy. Mind this: since every iteration can in the worst case double the number of items in keys, your program is actually of complexity O(2^n) where n is the array length.

In a matter of using more efficient structures you can also use Counter from collections that saves a bit of verbosity (it has zero as default value) and computation time (it is optimized C structure).

Without optimizing the algorithm, which I believe is part of the challenge :

from collections import Counter

class Solution:

    def findTargetSumWays(self, nums: List[int], S: int) -&gt; int:
        counts = Counter()
        counts[-nums[0]] += 1
        counts[nums[0]] += 1
        for num in nums[1:]:
            new = Counter()
            for key in counts.keys():
                new[key + num] += counts[key]
                new[key - num] += counts[key]
            counts = new
        return counts[S]