題目出處
難度
medium
個人範例程式碼
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
memo = {}
return self.dfs(nums, 0, target, memo)
def dfs(self, nums, start_idx, target, memo):
# end of recursion
if start_idx >= len(nums):
if target == 0:
return 1
else:
return 0
# memoization
if (start_idx, target) in memo:
return memo[(start_idx, target)]
# define and split
ans = self.dfs(nums, start_idx+1, target-nums[start_idx], memo) + self.dfs(nums, start_idx+1, target+nums[start_idx], memo)
# memoization
memo[(start_idx, target)] = ans
return ans
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
仔細看發現是很單純的「2 指數」的題目，
每一次我們都只要多延伸出「+」或「-」的新情況，
memoization
純 DFS 會 TLE，需要搭配 DP 的記憶化搜索，
我們紀錄的是，(目前 target 的值，目前的 idx)，
當進行一樣的 target 與同 idx 搜尋時，我們可以直接查表。
input handling
在 dfs 內處理
Boundary conditions
在 dfs 內控制範圍，我們在「搜尋 start_idx >= nums 總長」的情況下停止遞迴。