Skip to main content

494. Target Sum

题解

function findTargetSumWays(nums: number[], target: number): number {
let ans = 0

// 定义 dfs 函数的作用是在 nums index时,判断与 target 的关系
const dfs = (index, target) => {
if (index === nums.length && target === 0) {
ans++
return
}
if (index >= nums.length) {
return
}
// 选择加
dfs(index + 1, target - nums[index])
// 选择减
dfs(index + 1, target + nums[index])
}

dfs(0, target)

return ans
};

返回结果来表示数量,递归可memo

function findTargetSumWays(nums: number[], target: number): number {
const memo = {}

// 定义 dfs 函数的作用是在 nums index时,判断与 target 的关系
const dfs = (index, target): number => {
const memoKey = `${index}-${target}`
if (memo[memoKey] !== undefined) {
return memo[memoKey]
}
if (index === nums.length) {
if (target === 0) {
return 1
}
return 0
}
const res = dfs(index + 1, target - nums[index]) // 选择加
+ dfs(index + 1, target + nums[index]) // 选择减

memo[memoKey] = res

return res
}

return dfs(0, target)
};