Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 494 with 14 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 494 # by problem number
lcpy gen -s target_sum # by problem name
nums and an integer target.
You want to build an expression out of nums by adding one of the symbols + and - before each integer in nums and then concatenate all the integers.
nums = [2, 1], you can add a + before 2 and a - before 1 and concatenate them to build the expression +2-1.target.
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Input: nums = [1], target = 1
Output: 1
class Solution:
# Time: O(n * total)
# Space: O(total)
def find_target_sum_ways(self, nums: list[int], target: int) -> int:
total = sum(nums)
# P = sum of '+'. P - (total - P) = target -> P = (target + total) / 2.
if (target + total) % 2 != 0 or total < abs(target):
return 0
subset_sum = (target + total) // 2
# dp[s] = number of subsets summing to s
dp = [0] * (subset_sum + 1)
dp[0] = 1
for num in nums:
for s in range(subset_sum, num - 1, -1):
dp[s] += dp[s - num]
return dp[subset_sum]
| Time | Space |
|---|---|
| O(n * total) | O(total) |