I am trying to solve this problem
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
My working solution that times out:
class Solution: def findTargetSumWays(self, nums: List[int], S: int) -> int: ways = 0 def dfs(index, s): nonlocal ways if index == len(nums): if s == 0: ways +=1 else: dfs(index+1, s-nums[index]) dfs(index+1, s+nums[index]) dfs(0, S) return ways
How to optimize this in terms of time complexity?
Please refrain from commenting that the method can exist as a function on its own; this is the template that leetcode uses and can't be changed.