【Day42】494. 目标和

494. 目标和

给你一个整数数组 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 <= 100

题解:

还是动态规划

class Solution {
    int n;
    int ans = 0;
    int t;
public:
    int findTargetSumWays(vector& nums, int target) {
        n = nums.size();
        t = target;
        dfs(0,nums,  0);
        return ans;
    }
    void dfs(int u, vector  & nums, int s){
        if(u == n){
            if(s == t) ++ans;
            return;
        }
        dfs(u + 1, nums, s + nums[u]);
        dfs(u + 1, nums, s - nums[u]);
    }
};

   转载规则


《【Day42】494. 目标和》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day43】1049. 最后一块石头的重量 II 【Day43】1049. 最后一块石头的重量 II
1049. 最后一块石头的重量 II有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <=
2021-06-08
下一篇 
【Day41】474.一和零 【Day41】474.一和零
474. 一和零给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的大小,该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的
2021-06-06
  目录