leetcode-494. 目标和刷题笔记（c++）

落日映苍穹つ 2023-02-22 05:12 2阅读 0赞

#### 写在前面 ####

*  难度：中等
 *  `dfs`

#### 题目详情 ####

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
    
    返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
    
    示例：
    
    输入：nums: [1, 1, 1, 1, 1], S: 3
    输出：5
    解释：
    
    -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
    
    一共有5种方法让最终目标和为3。
     
    提示：
    
    数组非空，且长度不会超过 20 。
    初始的数组的和不会超过 1000 。
    保证返回的最终结果能被 32 位整数存下。

*  示例说明
    
     *  数组中每个元素有2种值，类似二叉树形结构，总路径数：`2^nums.size()`

#### ac代码 ####

class Solution
    {
        
    public:
        void dfs(vector<int>& nums, int S, int& cnt, int k, int sum)
        {
        
            if(k==nums.size())
            {
        
                if(sum==S)
                    cnt++;
                return;
            }
            dfs(nums, S, cnt, k+1, sum+nums[k]);
            dfs(nums, S, cnt, k+1, sum-nums[k]);
        }
        int findTargetSumWays(vector<int>& nums, int S)
        {
        
            int cnt=0;
            int sum=0;
            dfs(nums,S,cnt,0,sum);
            return cnt;
        }
    };

*  参考文章
    
     *  [LeetCode 494. 目标和（C++）][LeetCode 494. _C]

[LeetCode 494. _C]: https://blog.csdn.net/qq_27060423/article/details/85058656

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-494. 目标和

题目来源 [494. 目标和][494.] 思路 01背包问题是选或者不选，但本题是必须选，是选+还是选-。先将本问题转换为01背包问题。假设所有符号为+的

川长思鸟来/ 2024年03月25日 10:45/ 0 赞/ 58 阅读

相关 LeetCode - 494 目标和

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [494. 目标和 - 力扣（LeetCod

左手的ㄟ右手/ 2023年09月26日 22:19/ 0 赞/ 109 阅读

相关 Java实现 LeetCode 494 目标和

494. 目标和给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选

Love The Way You Lie/ 2023年07月17日 14:00/ 0 赞/ 4 阅读

相关 Leetcode刷题java之494. 目标和

执行结果：通过显示详情执行用时 :515 ms, 在所有 Java 提交中击败了20.09% 的用户内存消耗 :34.2 MB, 在所有 Java 提交中击败了

分手后的思念是犯贱/ 2023年07月04日 11:11/ 0 赞/ 14 阅读

相关 leetcode-494. 目标和刷题笔记（c++）

写在前面难度：中等 `dfs` 题目详情给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和

落日映苍穹つ/ 2023年02月22日 05:12/ 0 赞/ 3 阅读

相关 494. 目标和

题目： [494. 目标和][494.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text

不念不忘少年蓝@/ 2022年12月02日 01:12/ 0 赞/ 112 阅读

相关 494. 目标和

给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个表达式：例如，nums =

向右看齐/ 2022年10月05日 10:59/ 0 赞/ 145 阅读

相关 494. 目标和

2021-06-07 LeetCode每日一题链接：[https://leetcode-cn.com/problems/target-sum/][https_leetc

谁践踏了优雅/ 2022年10月05日 06:59/ 0 赞/ 160 阅读

相关 leetcode 494. Target Sum | 494. 目标和（动态规划）

题目 [https://leetcode.com/problems/target-sum/][https_leetcode.com_problems_target-sum

「爱情、让人受尽委屈。」/ 2022年09月10日 14:24/ 0 赞/ 152 阅读

相关 leetcode 494 目标和

前言题目：[494. 目标和][494.] 参考题解：[494. 目标和][494. 1] -------------------- 提交代码这道题目挺难

怼烎@/ 2022年08月28日 04:57/ 0 赞/ 147 阅读