target_sum
1from functools import cache 2 3 4# @leet start 5class Solution: 6 def findTargetSumWays(self, nums: list[int], target: int) -> int: 7 """ 8 This question asks us to find the number of ways to assign 9 addition or subtraction signs to a set of numbers num to get to a target. 10 We know that we can use dfs in $O(2^n)$ to do this, since for each number, 11 we can either add or subtract it from our running total. 12 13 If we add caching to this, we can reduce the time complexity to $O(t * n)$. 14 """ 15 n = len(nums) 16 17 @cache 18 def dfs(total, i): 19 if i == n: 20 return 1 if total == target else 0 21 else: 22 return dfs(total + nums[i], i + 1) + dfs(total - nums[i], i + 1) 23 24 return dfs(0, 0) 25 26 27# @leet end 28 29 30def test(): 31 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def findTargetSumWays(self, nums: list[int], target: int) -> int: 8 """ 9 This question asks us to find the number of ways to assign 10 addition or subtraction signs to a set of numbers num to get to a target. 11 We know that we can use dfs in $O(2^n)$ to do this, since for each number, 12 we can either add or subtract it from our running total. 13 14 If we add caching to this, we can reduce the time complexity to $O(t * n)$. 15 """ 16 n = len(nums) 17 18 @cache 19 def dfs(total, i): 20 if i == n: 21 return 1 if total == target else 0 22 else: 23 return dfs(total + nums[i], i + 1) + dfs(total - nums[i], i + 1) 24 25 return dfs(0, 0)
def
findTargetSumWays(self, nums: list[int], target: int) -> int:
7 def findTargetSumWays(self, nums: list[int], target: int) -> int: 8 """ 9 This question asks us to find the number of ways to assign 10 addition or subtraction signs to a set of numbers num to get to a target. 11 We know that we can use dfs in $O(2^n)$ to do this, since for each number, 12 we can either add or subtract it from our running total. 13 14 If we add caching to this, we can reduce the time complexity to $O(t * n)$. 15 """ 16 n = len(nums) 17 18 @cache 19 def dfs(total, i): 20 if i == n: 21 return 1 if total == target else 0 22 else: 23 return dfs(total + nums[i], i + 1) + dfs(total - nums[i], i + 1) 24 25 return dfs(0, 0)
This question asks us to find the number of ways to assign addition or subtraction signs to a set of numbers num to get to a target. We know that we can use dfs in $O(2^n)$ to do this, since for each number, we can either add or subtract it from our running total.
If we add caching to this, we can reduce the time complexity to $O(t * n)$.
def
test():