目标
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 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说明：
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
思路
有一个数组，可以在数组元素前加上正负号来组成表达式，问表达式等于target的数目。
如果当前元素为正则累加，否则相减，递归直到所有元素都已列入表达式，如果累加结果等于target则返回1，否则返回0。
//todo 改为递推，或记忆化搜索
代码
/**
* @date 2024-06-30 20:07
*/
public class FindTargetSumWays494 {
public int findTargetSumWays(int[] nums, int target) {
return dfs(nums, 1, nums[0], target) + dfs(nums, 1, -nums[0], target);
}
public int dfs(int[] nums, int i, int res, int target) {
if (i == nums.length) {
return res - target == 0 ? 1 : 0;
}
return dfs(nums, i + 1, res + nums[i], target) + dfs(nums, i + 1, res - nums[i], target);
}
}
性能
