目标和

[编程题]目标和

热度指数：2482 时间限制：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.保证返回的结果个数在整数范围内

数据范围:

$0<=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

输出

算法知识视频讲解

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)