Leetcode刷题java之494. 目标和

分手后的思念是犯贱 2023-07-04 11:11 13阅读 0赞

执行结果：

通过

显示详情

执行用时 :515 ms, 在所有 Java 提交中击败了20.09% 的用户

内存消耗 :34.2 MB, 在所有 Java 提交中击败了94.23%的用户

题目：

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

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: 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。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/target-sum  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

采用回溯法

代码：

class Solution {
        int result=0;
        public int findTargetSumWays(int[] nums, int S) {
            backtrack(nums,S,0);
            return result;
        }
        public void backtrack(int[] nums,int S,int length)
        {
            if(length==nums.length)
            {
                if(S==0)
                {
                    result++;
                    return;
                }else
                {
                    return;
                }
            }
            backtrack(nums,S-nums[length],length+1);
            backtrack(nums,S+nums[length],length+1);
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 494.目标和

![在这里插入图片描述][67f4b8e3f6ed4ccd9f395c038504f144.png] 1. 回溯算法这题和之前做的那些排列、组合的回溯稍微有些不同，你

旧城等待，/ 2024年03月26日 13:41/ 0 赞/ 52 阅读

相关 LeetCode-494. 目标和

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

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

相关 494. 目标和——【Leetcode每日刷题】

494. 目标和给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个表达式：

比眉伴天荒/ 2024年03月25日 10:44/ 0 赞/ 71 阅读

相关 LeetCode - 494 目标和

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

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

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

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

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

相关 494. 目标和

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

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

相关 494. 目标和

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

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

相关 494. 目标和

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

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

相关 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 赞/ 145 阅读