- 标签:数组、动态规划、回溯
- 难度:中等
描述:给定一个整数数组 +
或 -
。然后串联起来构造成一个表达式。
要求:返回通过上述方法构造的、运算结果等于
说明:
-
$1 \le nums.length \le 20$ 。 -
$0 \le nums[i] \le 1000$ 。 -
$0 \le sum(nums[i]) \le 1000$ 。 -
$-1000 \le target \le 1000$ 。
示例:
- 示例 1:
输入:nums = [1,1,1,1,1], target = 3
输出:5
解释:一共有 5 种方法让最终目标和为 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
- 示例 2:
输入:nums = [1], target = 1
输出:1
使用深度优先搜索对每位数字进行 +
或者 -
,具体步骤如下:
- 定义从位置
$0$ 、和为$0$ 开始,到达数组尾部位置为止,和为$target$ 的方案数为dfs(0, 0)
。 - 下面从位置
$0$ 、和为$0$ 开始,以深度优先搜索遍历每个位置。 - 如果当前位置
$i$ 到达最后一个位置$size$ :- 如果和
$cur\underline{\hspace{0.5em}}sum$ 等于目标和$target$ ,则返回方案数$1$ 。 - 如果和
$cur\underline{\hspace{0.5em}}sum$ 不等于目标和$target$ ,则返回方案数$0$ 。
- 如果和
- 递归搜索
$i + 1$ 位置,和为$cur\underline{\hspace{0.5em}}sum - nums[i]$ 的方案数。 - 递归搜索
$i + 1$ 位置,和为$cur\underline{\hspace{0.5em}}sum + nums[i]$ 的方案数。 - 将 4 ~ 5 两个方案数加起来就是当前位置
$i$ 、和为$cur\underline{\hspace{0.5em}}sum$ 的方案数,返回该方案数。 - 最终方案数为
dfs(0, 0)
,将其作为答案返回即可。
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
size = len(nums)
def dfs(i, cur_sum):
if i == size:
if cur_sum == target:
return 1
else:
return 0
ans = dfs(i + 1, cur_sum - nums[i]) + dfs(i + 1, cur_sum + nums[i])
return ans
return dfs(0, 0)
-
时间复杂度:$O(2^n)$。其中
$n$ 为数组$nums$ 的长度。 -
空间复杂度:$O(n)$。递归调用的栈空间深度不超过
$n$ 。
在思路 1 中我们单独使用深度优先搜索对每位数字进行 +
或者 -
的方法超时了。所以我们考虑使用记忆化搜索的方式,避免进行重复搜索。
这里我们使用哈希表
- 定义从位置
$0$ 、和为$0$ 开始,到达数组尾部位置为止,和为$target$ 的方案数为dfs(0, 0)
。 - 下面从位置
$0$ 、和为$0$ 开始,以深度优先搜索遍历每个位置。 - 如果当前位置
$i$ 遍历完所有位置:- 如果和
$cur\underline{\hspace{0.5em}}sum$ 等于目标和$target$ ,则返回方案数$1$ 。 - 如果和
$cur\underline{\hspace{0.5em}}sum$ 不等于目标和$target$ ,则返回方案数$0$ 。
- 如果和
- 如果当前位置
$i$ 、和为$cur\underline{\hspace{0.5em}}sum$ 之前记录过(即使用$table$ 记录过对应方案数),则返回该方案数。 - 如果当前位置
$i$ 、和为$cur\underline{\hspace{0.5em}}sum$ 之前没有记录过,则:- 递归搜索
$i + 1$ 位置,和为$cur\underline{\hspace{0.5em}}sum - nums[i]$ 的方案数。 - 递归搜索
$i + 1$ 位置,和为$cur\underline{\hspace{0.5em}}sum + nums[i]$ 的方案数。 - 将上述两个方案数加起来就是当前位置
$i$ 、和为$cur\underline{\hspace{0.5em}}sum$ 的方案数,将其记录到哈希表$table$ 中,并返回该方案数。
- 递归搜索
- 最终方案数为
dfs(0, 0)
,将其作为答案返回即可。
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
size = len(nums)
table = dict()
def dfs(i, cur_sum):
if i == size:
if cur_sum == target:
return 1
else:
return 0
if (i, cur_sum) in table:
return table[(i, cur_sum)]
cnt = dfs(i + 1, cur_sum - nums[i]) + dfs(i + 1, cur_sum + nums[i])
table[(i, cur_sum)] = cnt
return cnt
return dfs(0, 0)
-
时间复杂度:$O(2^n)$。其中
$n$ 为数组$nums$ 的长度。 -
空间复杂度:$O(n)$。递归调用的栈空间深度不超过
$n$ 。
假设数组中所有元素和为 +
的元素为 -
的元素和为
而
那么这道题就变成了,如何在数组中找到一个集合,使集合中元素和为
定义状态
填满容量为
- 不使用当前
$num$ :只使用之前元素填满容量为$i$ 的背包的方法数。 - 使用当前
$num$ :填满容量$i - num$ 的包的方法数,再填入$num$ 的方法数。
则动态规划的状态转移方程为:$dp[i] = dp[i] + dp[i - num]$。
初始状态下,默认填满容量为
根据状态定义,最后输出
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
sum_nums = sum(nums)
if abs(target) > abs(sum_nums) or (target + sum_nums) % 2 == 1:
return 0
size = (target + sum_nums) // 2
dp = [0 for _ in range(size + 1)]
dp[0] = 1
for num in nums:
for i in range(size, num - 1, -1):
dp[i] = dp[i] + dp[i - num]
return dp[size]
-
时间复杂度:$O(n)$,其中
$n$ 为数组$nums$ 的长度。 - 空间复杂度:$O(n)$。