首页 > 试题广场 >

目标和

[编程题]目标和

热度指数：2834 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整数数组nums和一个整数target，请你返回该数组能构成多少种不同的表达式等于target。

规则如下：

1.将数组里每个整数前面可以添加"+"或者"-"符号，组成一个表达式，例如[1,2]，可以变成”+1+2","+1-2","-1+2","-1-2"，这四种

2.只能添加"+"与"-"符号，不能添加其他的符号

3.如果构不成等于target的表达式，请返回0

4.保证返回的结果个数在整数范围内

数据范围:

$1<=nums.length<=20$

$0<=nums[i]<=1000$

$0<=sum(nums[i])<=1000$

$-1000<=target<=1000$

示例1

输入

[1,1,1,2],3

输出

说明

-1 + 1 + 1 + 2 = 3
+1 - 1 + 1 + 2 = 3
+1 + 1 - 1 + 2 = 3

示例2

输入

[2],2

输出

算法知识视频讲解

Java

pein531

从左往右的尝试模型，数据量很小，直接暴力递归能过。

暴力递归

每一层递归可以选择对当前数添加或不添加负号，将其累加到结果上，直到凑出target，就生成一种方法。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int findTargetSumWays (int[] nums, int target) {
        // write code here
        if(nums == null || nums.length == 0) return 0;
        return dfs(nums, 0, target);
    }
    
    private int dfs(int[] nums, int index, int rest) {
        if(index == nums.length){
            return rest == 0? 1: 0;     // 到最后一个数如果rest为0了，就形成了一种合法的方案
        }
        // 否则就给当前的数加上负号或不加负号累加到rest上，继续尝试下面的数
        return dfs(nums, index + 1, rest + nums[index]) + dfs(nums, index + 1, rest - nums[index]);
    }
}

记忆化搜索

根据递归逻辑可以用缓存法改出一版记忆化搜索，避免重复的递归展开计算。理论上来说，记忆化搜索的速度应该是更快的，在leetcode上把这一题改成记忆化搜索后，可以快9倍左右，但是牛客上可能数据量比较小，反而更慢了。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int findTargetSumWays (int[] nums, int target) {
        // write code here
        if(nums == null || nums.length == 0) return 0;
        int n = nums.length;
        HashMap<Integer, HashMap<Integer, Integer>> mem = new HashMap<>();
        return dfs(nums, 0, target, mem);
    }
    
    private int dfs(int[] nums, int index, int rest, HashMap<Integer, HashMap<Integer, Integer>> mem) {
        if(mem.containsKey(index) && mem.get(index).containsKey(rest)) {
            return mem.get(index).get(rest);    // 缓存命中，直接返回
        }
        if(index == nums.length){
            return rest == 0? 1: 0;     // 到最后一个数如果rest为0了，就形成了一种合法的方案
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        // 否则就给当前的数加上负号或不加负号累加到rest上，继续尝试下面的数
        int res = dfs(nums, index + 1, rest + nums[index], mem) + dfs(nums, index + 1, rest - nums[index], mem);
        map.put(rest, res);
        mem.put(index, map);
        return res;
    }
}

动态规划

这个题如果直接根据记忆化搜索的递归逻辑改成动态规划是没什么收益的，考虑到rest会取到负数，缓存无论如何都需要使用哈希表，这无疑就增加了取值的常数时间。这样改出来的动态规划没有任何优势。

因此我们需要分析一下业务：记原始数组所有元素的累加和为sum，假设我们对所有数添加完正负号之后凑出了目标和target，此时数组中有P个正数，N个负数。则有如下两式成立

$P+N=target$

$P-N=sum$

联立两式得到 $P=\frac{sum+target}{2}$ ，这时候问题就转化为：从数组中选择若干数，能凑出P的方案数，成为了一个纯背包问题。同时还有两个点可以优化常数时间：(1)如果sum比target的绝对值还小，肯定没有凑数方法。(2)如果sum和target的奇偶性不同，肯定也没有凑数方法。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int findTargetSumWays (int[] nums, int target) {
        // write code here
        if(nums == null || nums.length == 0) return 0;
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if(sum < Math.abs(target) || ((sum + target) & 1) != 0) {
            // sum不足target的绝对值，或sum和target奇偶性不同，直接返回0
            return 0;
        }
        int upBound = (sum + target) >> 1;
        int[] dp = new int[upBound + 1];
        dp[0] = 1;    // base case凑出0有1种方案:什么数都不选
        for(int num: nums){
            for(int i = upBound; i >= num; i--){
                dp[i] += dp[i - num];
            }
        }
        return dp[upBound];
    }
}

编辑于 2022-01-05 09:30:35 回复(0)

Python3

liangzhengjie

经典回溯算法

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def findTargetSumWays(self , nums: List[int], target: int) -> int:
        # write code here
        if len(nums) == 0 and target == 0:
            return 0
            
        res = self.traverse(nums, 0, 0, target)
        
        return res
        

    def traverse(self, nums, n, now,  target):
        if n == len(nums) and now == target:
            return 1

        if n >= len(nums):
            return 0

        res = 0
        res += self.traverse(nums, n + 1, now + nums[n], target)
        res += self.traverse(nums, n + 1, now - nums[n], target)

        return res

编辑于 2024-04-15 22:38:55 回复(0)

C++

Anron_

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int count=0;
    void dfs(vector<int>& nums,int id,int target,int sum)
    {
        if(id==nums.size() ){
            if(sum==target)
                count++;
            // return;
        }
        else{
            dfs(nums,id+1,target,sum+nums[id]);
            dfs(nums,id+1,target,sum-nums[id]);
        }
        
        
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        // write code here
        if(nums.size()==0) return 0;
        dfs(nums,0,target,0);
        return count;
    }
};

发表于 2024-01-31 18:45:49 回复(0)

空中转体一周半

递归解题：每个数都加上正负号参与求和，如果最后的和等于target，则种类+1。

import java.util.*;
public class Solution {
    public int findTargetSumWays (int[] nums, int target) {
        return func(nums, 0, target, 0);
    }
    public int func(int []nums, int index, int target, int cur) {
        if(index >= nums.length) return 0;
        int count = 0;
        if(cur + nums[index] == target && index == nums.length - 1) {
            count++;
        }
        if(cur - nums[index] == target && index == nums.length - 1) {
            count++;
        }
        if(index == nums.length - 1) return count;
        return func(nums, index + 1, target, cur + nums[index]) + func(nums, index + 1, target, cur - nums[index]);
    }
}

发表于 2023-04-17 15:31:26 回复(0)

小谷围做题家

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param target int整型 
 * @return int整型
*/
func findTargetSumWays( nums []int ,  target int ) int {
    if len(nums)==0{
        return 0
    }
    cnt:=0
    var back_tracking func(int,int)
    back_tracking=func(sum int,idx int){
        if idx==len(nums){
            if sum==target{
                cnt++
            }
            return
        }
        back_tracking(sum+nums[idx],idx+1)
        back_tracking(sum-nums[idx],idx+1)
    }
    back_tracking(0,0)
    return cnt
}

发表于 2023-03-09 23:36:24 回复(0)

Java

blue&&lan

public int findTargetSumWays (int[] nums, int target) {
        if(nums.length==0)return 0;
        findT(nums,0,target);
        return n;
    }
    
    void findT(int[] nums,int i,int s){
        if(i==nums.length){
            if(s==0)n++;
            return;
        }else {
            s+=(-1)*nums[i];
            findT(nums,i+1,s);
            s-=(-1)*nums[i];
            s+=nums[i];
            findT(nums,i+1,s);
            s-=nums[i];
        }
    }

发表于 2022-05-20 19:30:40 回复(0)

C++

yang_xiao

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int findTargetSumWays(vector<int>& nums, int target) {
        // write code here
        if(!nums.size()) return 0;
        return test(nums,target,nums.size()-1);
    }
    
    int test(vector<int>& nums,int target,int n){
        //出口
        if(n == -1){
            if(target == 0) return 1;
            else return 0;
        }
        
        return test(nums,target - nums[n],n - 1) + test(nums,target + nums[n], n - 1);
    }
};

发表于 2022-02-22 19:33:07 回复(0)

Oo啊哈

class Solution:
    def __init__(self):
        self.count=0
        
    def findTargetSumWays(self , nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return 0
        self.backtrack(nums, target, 0, 0)
        return self.count;
        # write code here
    def backtrack(self ,  nums: List[int], target: int, index: int, sum: int):
        if index == len(nums):
            if sum == target:
                self.count+=1
        else :
            self.backtrack(nums, target, index + 1, sum + nums[index])
            self.backtrack(nums, target, index + 1, sum - nums[index])

发表于 2021-12-30 11:58:54 回复(0)

Java

倔强小头

public int findTargetSumWays(int[] nums, int target) {
        if(nums.length==0) return 0;
        solve(0, nums, target);
        return ncount;
    }
    int ncount = 0;
    public void solve(int idx, int[] nums, int target) {
        if (idx == nums.length && target == 0) {
            ncount++;
            return;
        }
        if (idx == nums.length) return;
        solve(idx+1, nums, target-nums[idx]); // nums[idx]符号为正
        solve(idx+1, nums, target+nums[idx]); // nums[idx]符号为负
    }

发表于 2021-12-28 11:06:02 回复(0)

提交观点

问题信息

动态规划数组递归

上传者：牛客301499号

难度：

9条回答 53收藏 4428浏览

通过挑战的用户

查看代码

已注销

2023-03-05 10:41:07
ৡ晨ꦿ᭄࿐

2022-09-14 14:31:37
Asphyxiay

2022-09-14 01:44:47
正在卷的乌龟很刻苦

2022-09-13 15:23:25
亮里格亮

2022-09-13 15:17:03

目标和

输入

输出

说明

输入

输出

暴力递归

记忆化搜索

动态规划

问题信息

热门推荐

通过挑战的用户

相关试题