用加法或者减法计算

发表于 | 更新于 | 分类于

用加法或者减法计算

Question

LeetCode第494题。

给你由n个非负的整数a1, a2, …, an组成的数组，以及另外一个整数S，你可以在每个整数前面添上+或者-得到一个算数表达式。请问总共有多少中方法使得表达式的计算结果是S。

例如，输入数组{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

Analysis

  • 回溯法(DFS)

    逐一扫描这个数组。对每个数字，我们都有两个选择，一是在这个数字前面添加加号，二是在这个数字前面添加减号。当给这个数字添加加号或者减号之后，我们再接着扫描下一个数字。因此这是典型的能用回溯法（回溯法也是DFS）解决的问题，可以用递归解决。
    对于数组中的每个数字都有2个选择，因此如果数组的长度是n，那么这个解法的时间复杂度就是O(2^n)。
    由于回溯法的时间复杂度很高，在用回溯法解题的时候如果有可能应尽量剪枝避免不比较的计算。此处如果数组中使用加法的最大和仍小于目标值时，此时不可能存在一组加减法使得结果为目标值，所以可以以此条件来判定从而减少回溯次数。

  • 动态规划

    假设我们把在前面添加加号的数字单独拿出来，它们的和记为p。剩下的数字我们在它们的前面都添加减号。这些添加减号的数字的和，我们用n表示。按照题目的要求，p-n=S。我们不难求得数组中所有数字的和，记为sum，并且有p+n=sum，也就是n=sum-p。把n=sum-p代入p-n=S中，得到p-(sum-p)=S，也就是p=(S+sum)/2。

    分析到这里，我们发现这个题目实际上是求解在数组中有多少种方法可以找出若干数字使得它们的和等于p（即(S+sum)/2）。这是典型的0-1背包问题，可以用动态规划求解。
    我们定义函数f(i,j)表示数组中前i个数字中选出若干个和为j的数字的方法总数。我们分析就能知道f(i,j)=f(i-1,j)+f(i-1,j-nums[i])。这是因为当我们在考虑第i个数字的时候，有两种选择，一个是不选第i个数字，此时f(i,j)=f(i-1,j)。另一种是我们选择第i个数字，此时f(i,j)=f(i-1,j-nums[i])，也就是在前i-1个数字中选出若干个和为j-nums[i]的方法总数。

    我们可以定义一个二维数组，它的行数为数组长度n加1，列数为数字之和p加1的。该数组的第i行第j列是函数f(i,j)的结果。我们再仔细分析发现，我们在求解f(i,j)时只需要用到该二维数组里的第i-1行。并且如果在同一行里我们从右到左求解，我们发现f(i-1,j)在求解完f(i,j)之后再也不需要了。因此我们实际上只需要保留二维数组中的一行就够了，可以减少空间的开销。

    如果数组的长度是n，从数组中选出的数字的目标和为p，那么上述基于动态规划的解法的时间复杂度是O(np)，而空间复杂度是O(p)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def find_target_sum_ways(list_a, target, n=0):
    val = list_a[0]
    if sum(list_a)< abs(target):
        return n
    if len(list_a)==1:
        if target == val or target == -val:
            n += 1
    if len(list_a)>1:
        list_a = list_a[1:]
        n = find_target_sum_ways(list_a, target - val, n)
        n = find_target_sum_ways(list_a, target + val, n)
    return n

list_a = [1,1,1,1,1]
n = find_target_sum_ways(list_a, 3)
print(n)
5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import numpy as np

def subset_sum(list_a, p):
    list_sum = np.zeros(p+1, np.int8)
    list_sum[0] = 1
    for i in list_a:
        for j in range(p):
            if p-j < i:
                continue
            list_sum[p-j] += list_sum[p-j-i]
    return list_sum[p]

def find_target_sum_ways_dp(list_a, target):
    if sum(list_a)< abs(target):
        return 0
    if (sum(list_a)+target)%2==1:
        return 0
    p = (sum(list_a)+target)//2
    n = subset_sum(list_a, p)
    return n
        
list_a = [1,1,1,1,1]
n = find_target_sum_ways_dp(list_a, 3)
print(n)
5