Target Sum
You are given an integer array 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.
For example, if nums =[2, 1], you can add a '+' before 2 and a '-' before 1 and
concatenate them to build the expression "+2-1".
Return the number of different expressions that you can build, which evaluates to target.
Example 1:
Input: nums =[1,1,1,1,1], target=3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
Solution: Returns the number of different expressions (int)
from typing import Listclass Solution: def find_target_sum)ways(self, nums: List[int], target : int)-> int: dp ={} # (index, total) -> # of ways def backtrack(i, total): if i == len(nums): return 1 if total == target else 0 if (i, total) in dp: return dp[(i, total)] dp[(i, total)] = (backtrack(i + 1, total + nums[i]) + backtrack(i +1, total - nums[i])) return dp[(i, total)] return backtrack(0, 0)Solution: Returns the actual different expressions (List)
from typing import Listclass Solution: def find_target_sum_ways_2(self, nums: List[int], target: int) -> List[List[int]]: def backtrack(i, total, way):
if i == len(nums): if total == target: return [way] # Return the way as a list return [] ways_with_plus = backtrack(i + 1, total + nums[i], way + [nums[i]])
ways_with_minus = backtrack(i + 1, total - nums[i], way + [-nums[i]]) return ways_with_plus + ways_with_minus return backtrack(0, 0, way=[])Code Walkthrough
The code is a recursive solution to find all the distinct ways to reach a target sum using a given list of numbers. Let's go through the code and its logic step by step:
Class Definition
The code defines a class named Solution that contains the method find_target_sum_ways. This method takes two parameters: nums, which is a list of numbers, and target, which is the target sum.
Recursive Backtracking
The main part of the code is the backtrack function, which is a recursive function. It explores different possibilities by adding or subtracting each number in the list to/from the total sum.
i - represents the current index in the nums list.
total - represents the current total sum.
way - is a list that keeps track of the path of numbers that lead to the current total.
Base Cases
If i is equal to the length of nums, it means we have reached the end of the list. In this case, we check whether the current total is equal to the target.
If it is, we return a list(way), representing a valid path. Otherwise, we return an empty list.
Recursive Calls
We make two recursive calls for each number at the current index i:
One call with the number added to the total and appended to the way list (representing a '+' operation).
Another call with the number subtracted from the total and its negation appended to the way list (representing a '-' operation).
We combine the results of these two calls by adding the lists together.
Return Value
The backtrack function returns a list of all possible ways to reach the target sum.
Method Invocation
The find_target_sum_ways method initializes the recursion by calling backtrack(0, 0, way=[]) with an initial index of 0, total sum of 0, and an empty way list to start.
Testing
The code demonstrates its use by providing an example with the nums list [1, 1, 1, 1, 1] and a target of 3. It then prints all the distinct ways to reach the target sum by iterating through the results returned by the find_target_sum_ways method.
The code works by exploring all possible combinations of adding and subtracting numbers in the nums list and keeps track of the path (in the way list) to each valid target sum. It successfully finds and prints all such paths.
nums = [1, 1, 1, 1, 1]target = 3solution = Solution()ways = solution.find_target_sum_ways_2(nums, target)for way in ways: print(" ".join(map(str, way)))