python - 如何生成在向量的数字之间添加 + 和 - 的所有可能性，因此总和应该是正数，使用回溯
python - How to generate all possibilities of adding + and - between numbers of a vector so the sum should be positive, using backtracking
我必须制作一个 python 应用程序，该应用程序生成在向量的数字之间添加 + 和 - 的所有可能性，因此总和应该是正数，使用回溯。我写在这里是因为我不太明白怎么做。
作为输入，我的应用程序获取整数向量：a1、a2、... an。
我举了一个回溯应该如何工作的例子，但我不知道是否可以实现。
（示例）对于 5 个数字：
a1 a2 a3 a4 a5
a1 + a2 + a3 + a4 + a5
a1 - a2 + a3 + a4 + a5
a1 - a2 - a3 + a4 + a5
a1 - a2 - a3 - a4 + a5
a1 - a2 - a3 - a4 - a5
a1 + a2 - a3 + a4 + a5
a1 + a2 - a3 - a4 + a5
a1 + a2 - a3 - a4 - a5
a1 + a2 + a3 - a4 + a5
a1 + a2 + a3 - a4 - a5
a1 + a2 + a3 + a4 - a5
这是我已经写的：
def first():
return int(a[0])
def next(nr):
return int(a[nr+1])
def sum(x):
suma = 0
for i in range(0,len(x)):
suma += x[i]
if(suma <= 0):
return False
return True
def equal(x):
for i in range(0,len(x)-1):
for j in range(i+1,len(x)):
if(x[i]==x[j]):
return False
return True
def isSet(x):
if equal(x) == False:
return False
return True
def consistent(x,dim):
return isSet(x)
def solution(x,dim):
return len(x) == dim and sum(x)
def solutionFound(x,dim):
print(x)
def backtracking(x,dim):
# ---idea of code that doesn't work
x=[first()] #candidate solution
nr = -1
while len(x)>0:
choosed = False
while not choosed and x[-1] < dim and nr < dim-1:
x[-1] = next(nr) #increase the last component
nr += 1
choosed = consistent(x, dim)
if choosed:
if solution(x, dim):
solutionFound(x, dim)
x.append(first()) # expand candidate solution
else:
nr -= 1
x = x[:-1] #go back one component
---
a = input(">>> write numbers: ").split()
n = len(a)
backtracking([],n)
如果您有任何想法，这可能是一个真正的帮助。感谢您的宝贵时间，祝您新年快乐！
L.E.: 非常感谢大家的回答。您帮助我对 python 语言有了更多的了解。
一种可能是在将最后一个元素添加到当前表达式列表之前计算总和。如果加上最后一个值的总和为正，则可以生成表达式列表：
ops = {'+':lambda x, y:x+y, '-':lambda x, y:x-y}
def _eval(d):
return d[0] if len(d) == 1 else _eval([ops[d[1]](d[0], d[2]), *d[3:]])
def combos(vals, l, c = []):
if not vals:
yield c
else:
for i in ['+', '-']:
if len(c) < l-1 or _eval([*c, i, vals[0]]) > 0:
yield from combos(vals[1:], l, c+[i, vals[0]])
print(list(combos([1, 2, 3, 4, 5], 5, [1])))
输出：
[[1, '+', 1, '+', 2, '+', 3, '+', 4, '+', 5],
[1, '+', 1, '+', 2, '+', 3, '+', 4, '-', 5],
[1, '+', 1, '+', 2, '+', 3, '-', 4, '+', 5],
[1, '+', 1, '+', 2, '-', 3, '+', 4, '+', 5],
[1, '+', 1, '-', 2, '+', 3, '+', 4, '+', 5],
[1, '+', 1, '-', 2, '+', 3, '+', 4, '-', 5],
[1, '-', 1, '+', 2, '+', 3, '+', 4, '+', 5],
[1, '-', 1, '+', 2, '+', 3, '+', 4, '-', 5],
[1, '-', 1, '+', 2, '+', 3, '-', 4, '+', 5],
[1, '-', 1, '-', 2, '+', 3, '+', 4, '+', 5]]
根据您的评论，有效序列的要求是求和结束时为正。中间结果可以是负数没关系。
因此，我要做的是创建一棵二叉树，其级别等于一个变量，二元决策为 + 或 - 下一个变量（即左 = - 和右 = +）。叶节点将等于遍历每条路径的总和。一旦构建了这样一棵树，您唯一需要做的就是遍历树并到达叶子。
这就是 回溯 的用武之地，因为一旦您到达叶节点并输出结果，您就需要 return 并回溯以测试另一种可能性。这种回溯可以很容易地使用递归实现，并以休假为基本情况。要在最后输出完整的总和，您可以将与节点标签和到目前为止所用路径相对应的字符串列表作为参数。
希望对您有所帮助！
使用itertools:
import itertools
v=[3,5,-7,2,-3,1,-1]
def next_combination(v):
v=[str(el) for el in v]
for op in itertools.product(["-","+"], repeat=len(v)-1):
x=list(itertools.chain.from_iterable(zip(v,op))) + [v[-1]]
if(eval(''.join(x))>0):
yield x
for el in next_combination(v):
print(el)
输出：
['3', '-', '5', '-', '-7', '-', '2', '-', '-3', '-', '1', '-', '-1']
['3', '-', '5', '-', '-7', '-', '2', '-', '-3', '-', '1', '+', '-1']
['3', '-', '5', '-', '-7', '-', '2', '-', '-3', '+', '1', '-', '-1']
['3', '-', '5', '-', '-7', '-', '2', '-', '-3', '+', '1', '+', '-1']
['3', '-', '5', '-', '-7', '-', '2', '+', '-3', '+', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '-', '-3', '-', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '-', '-3', '-', '1', '+', '-1']
['3', '-', '5', '-', '-7', '+', '2', '-', '-3', '+', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '-', '-3', '+', '1', '+', '-1']
['3', '-', '5', '-', '-7', '+', '2', '+', '-3', '-', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '+', '-3', '-', '1', '+', '-1']
['3', '-', '5', '-', '-7', '+', '2', '+', '-3', '+', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '+', '-3', '+', '1', '+', '-1']
['3', '+', '5', '-', '-7', '-', '2', '-', '-3', '-', '1', '-', '-1']
['3', '+', '5', '-', '-7', '-', '2', '-', '-3', '-', '1', '+', '-1']
['3', '+', '5', '-', '-7', '-', '2', '-', '-3', '+', '1', '-', '-1']
['3', '+', '5', '-', '-7', '-', '2', '-', '-3', '+', '1', '+', '-1']
['3', '+', '5', '-', '-7', '-', '2', '+', '-3', '-', '1', '-', '-1']
['3', '+', '5', '-', '-7', '-', '2', '+', '-3', '-', '1', '+', '-1']
['3', '+', '5', '-', '-7', '-', '2', '+', '-3', '+', '1', '-', '-1']
['3', '+', '5', '-', '-7', '-', '2', '+', '-3', '+', '1', '+', '-1']
['3', '+', '5', '-', '-7', '+', '2', '-', '-3', '-', '1', '-', '-1']
['3', '+', '5', '-', '-7', '+', '2', '-', '-3', '-', '1', '+', '-1']
['3', '+', '5', '-', '-7', '+', '2', '-', '-3', '+', '1', '-', '-1']
['3', '+', '5', '-', '-7', '+', '2', '-', '-3', '+', '1', '+', '-1']
['3', '+', '5', '-', '-7', '+', '2', '+', '-3', '-', '1', '-', '-1']
['3', '+', '5', '-', '-7', '+', '2', '+', '-3', '-', '1', '+', '-1']
['3', '+', '5', '-', '-7', '+', '2', '+', '-3', '+', '1', '-', '-1']
['3', '+', '5', '-', '-7', '+', '2', '+', '-3', '+', '1', '+', '-1']
['3', '+', '5', '+', '-7', '-', '2', '-', '-3', '-', '1', '-', '-1']
['3', '+', '5', '+', '-7', '-', '2', '-', '-3', '+', '1', '-', '-1']
['3', '+', '5', '+', '-7', '-', '2', '-', '-3', '+', '1', '+', '-1']
['3', '+', '5', '+', '-7', '+', '2', '-', '-3', '-', '1', '-', '-1']
['3', '+', '5', '+', '-7', '+', '2', '-', '-3', '-', '1', '+', '-1']
['3', '+', '5', '+', '-7', '+', '2', '-', '-3', '+', '1', '-', '-1']
['3', '+', '5', '+', '-7', '+', '2', '-', '-3', '+', '1', '+', '-1']
['3', '+', '5', '+', '-7', '+', '2', '+', '-3', '+', '1', '-', '-1']
Searches through binary tree of (+/-) using a function search.
预先计算数组中每个索引到末尾的绝对值之和，允许在搜索中终止于中间节点。
这是因为如果到目前为止的值之和 + 从当前索引到数组末尾的值的累计值 < 0，那么我们知道剩余数组中没有足够的值来克服当前的负累加值。
def findsums(a, n = -1, sumsofar = 0, signs = [], results = [], cumsum = []):
"""
finds additions and subtraction of array element which are >= 0
a - input array\n
n - highest index element of array we\'re using on the previous iteration
sumsofar - sum using element up to index
signs - signs (+/-) applied to these eleemnt
results - solutions
cumsum - cumulative sum of elements from index i to the end of array
"""
if not cumsum:
# Base case getting started
#
# Cumulative so of a in reverse order
cumsum = cumsum_calc(a)
# Use the first number as-is (i.e. no +/- sign)
signs = [''] # first element is a
sumsofar = a[0]
n = 0
# terminal case
if n >= len(a)-1:
if sumsofar >= 0:
# terminal case (valid solution, so add)
results.append(signs[:])
else:
# invalid solution
pass # nothing to do
elif n == -1 or sumsofar + cumsum[n] >= 0:
# Viable candidate so far
# Try +/- alternatives\n
# Try + sign
signs.append(' + ')
findsums(a, n+1, sumsofar+a[n+1], signs, results, cumsum)
signs.pop()
# Try '-' sign
signs.append(' - ')
findsums(a, n+1, sumsofar-a[n+1], signs, results, cumsum)
signs.pop()
else:
# Backtrack (sumsofar + cumsum[n] < 0):
# No valid solution going forward\n
# So don\'t go any further with this sequence
pass
return results
def cumsum_calc(arr):
" accum sum from next index forward in the array "
# Adepted from https://www.geeksforgeeks.org/python-program-to-find-cumulative-sum-of-a-list/\n
# maximum sum of elements after i
b = [abs(x) for x in arr]
return [sum(b[i+1:]) for i in range(len(b)+1)]
def show_solutions(a, signs):
" intertwines signs and array to show how they are added "
# convert a to string, with parentheses around negative values
converta = list(map(str, a))
# place sign before each value in array a (converta)
# function to generate list of sign, value pairs
create_sign_value_pairs = lambda sign: list(zip(sign, converta))
# Create sign/value pairs (i.e. [[('+', '(-1)'), ('+', '2')],...]
sol_with_signs = list(map(create_sign_value_pairs, signs))
# Convert each solution to a string
solutions = list(map(lambda sol: ' '.join([''.join(s) for s in sol]), sol_with_signs))
return "\t" + '\n\t'.join(solutions)
tests = [[2, 3], [-1, 2], [1], [-1], [-1, -2], [1, 2, 3, 4, -5]]
示例用法
测试 = [[2, 3], [-1, 2], [1], [-1], [-1, -2], [1, 2, 3, 4, -5] ]
测试中的 t：
s = findsums(t, 结果 = [])
打印（"For array {}, solutions are:".格式（t））
打印（show_solutions（t，s））
输出
For array [2, 3], solutions are:
2 + 3
For array [-1, 2], solutions are:
-1 + 2
For array [1], solutions are:
1
For array [-1], solutions are:
For array [-1, -2], solutions are:
-1 - -2
For array [1, 2, 3, 4, -5], solutions are:
1 + 2 + 3 + 4 + -5
1 + 2 + 3 + 4 - -5
1 + 2 + 3 - 4 - -5
1 + 2 - 3 + 4 - -5
1 + 2 - 3 - 4 - -5
1 - 2 + 3 + 4 + -5
1 - 2 + 3 + 4 - -5
1 - 2 + 3 - 4 - -5
1 - 2 - 3 + 4 - -5
性能
有：arr = [-1, 1, 2, 3, 3, 1,3, 34,2,1,2,-4, -9, 2, 11]
使用 Grzegorz Skibinski（组合方法）
760 ms ± 12.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
当前方法（使用回溯）
72.1 ms ± 2.34 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
使用回溯比测试所有组合快 10 倍
我必须制作一个 python 应用程序，该应用程序生成在向量的数字之间添加 + 和 - 的所有可能性，因此总和应该是正数，使用回溯。我写在这里是因为我不太明白怎么做。
作为输入，我的应用程序获取整数向量：a1、a2、... an。
我举了一个回溯应该如何工作的例子，但我不知道是否可以实现。
（示例）对于 5 个数字：
a1 a2 a3 a4 a5
a1 + a2 + a3 + a4 + a5
a1 - a2 + a3 + a4 + a5
a1 - a2 - a3 + a4 + a5
a1 - a2 - a3 - a4 + a5
a1 - a2 - a3 - a4 - a5
a1 + a2 - a3 + a4 + a5
a1 + a2 - a3 - a4 + a5
a1 + a2 - a3 - a4 - a5
a1 + a2 + a3 - a4 + a5
a1 + a2 + a3 - a4 - a5
a1 + a2 + a3 + a4 - a5
这是我已经写的：
def first():
return int(a[0])
def next(nr):
return int(a[nr+1])
def sum(x):
suma = 0
for i in range(0,len(x)):
suma += x[i]
if(suma <= 0):
return False
return True
def equal(x):
for i in range(0,len(x)-1):
for j in range(i+1,len(x)):
if(x[i]==x[j]):
return False
return True
def isSet(x):
if equal(x) == False:
return False
return True
def consistent(x,dim):
return isSet(x)
def solution(x,dim):
return len(x) == dim and sum(x)
def solutionFound(x,dim):
print(x)
def backtracking(x,dim):
# ---idea of code that doesn't work
x=[first()] #candidate solution
nr = -1
while len(x)>0:
choosed = False
while not choosed and x[-1] < dim and nr < dim-1:
x[-1] = next(nr) #increase the last component
nr += 1
choosed = consistent(x, dim)
if choosed:
if solution(x, dim):
solutionFound(x, dim)
x.append(first()) # expand candidate solution
else:
nr -= 1
x = x[:-1] #go back one component
---
a = input(">>> write numbers: ").split()
n = len(a)
backtracking([],n)
如果您有任何想法，这可能是一个真正的帮助。感谢您的宝贵时间，祝您新年快乐！
L.E.: 非常感谢大家的回答。您帮助我对 python 语言有了更多的了解。
一种可能是在将最后一个元素添加到当前表达式列表之前计算总和。如果加上最后一个值的总和为正，则可以生成表达式列表：
ops = {'+':lambda x, y:x+y, '-':lambda x, y:x-y}
def _eval(d):
return d[0] if len(d) == 1 else _eval([ops[d[1]](d[0], d[2]), *d[3:]])
def combos(vals, l, c = []):
if not vals:
yield c
else:
for i in ['+', '-']:
if len(c) < l-1 or _eval([*c, i, vals[0]]) > 0:
yield from combos(vals[1:], l, c+[i, vals[0]])
print(list(combos([1, 2, 3, 4, 5], 5, [1])))
输出：
[[1, '+', 1, '+', 2, '+', 3, '+', 4, '+', 5],
[1, '+', 1, '+', 2, '+', 3, '+', 4, '-', 5],
[1, '+', 1, '+', 2, '+', 3, '-', 4, '+', 5],
[1, '+', 1, '+', 2, '-', 3, '+', 4, '+', 5],
[1, '+', 1, '-', 2, '+', 3, '+', 4, '+', 5],
[1, '+', 1, '-', 2, '+', 3, '+', 4, '-', 5],
[1, '-', 1, '+', 2, '+', 3, '+', 4, '+', 5],
[1, '-', 1, '+', 2, '+', 3, '+', 4, '-', 5],
[1, '-', 1, '+', 2, '+', 3, '-', 4, '+', 5],
[1, '-', 1, '-', 2, '+', 3, '+', 4, '+', 5]]
根据您的评论，有效序列的要求是求和结束时为正。中间结果可以是负数没关系。
因此，我要做的是创建一棵二叉树，其级别等于一个变量，二元决策为 + 或 - 下一个变量（即左 = - 和右 = +）。叶节点将等于遍历每条路径的总和。一旦构建了这样一棵树，您唯一需要做的就是遍历树并到达叶子。
这就是 回溯 的用武之地，因为一旦您到达叶节点并输出结果，您就需要 return 并回溯以测试另一种可能性。这种回溯可以很容易地使用递归实现，并以休假为基本情况。要在最后输出完整的总和，您可以将与节点标签和到目前为止所用路径相对应的字符串列表作为参数。
希望对您有所帮助！
使用itertools:
import itertools
v=[3,5,-7,2,-3,1,-1]
def next_combination(v):
v=[str(el) for el in v]
for op in itertools.product(["-","+"], repeat=len(v)-1):
x=list(itertools.chain.from_iterable(zip(v,op))) + [v[-1]]
if(eval(''.join(x))>0):
yield x
for el in next_combination(v):
print(el)
输出：
['3', '-', '5', '-', '-7', '-', '2', '-', '-3', '-', '1', '-', '-1']
['3', '-', '5', '-', '-7', '-', '2', '-', '-3', '-', '1', '+', '-1']
['3', '-', '5', '-', '-7', '-', '2', '-', '-3', '+', '1', '-', '-1']
['3', '-', '5', '-', '-7', '-', '2', '-', '-3', '+', '1', '+', '-1']
['3', '-', '5', '-', '-7', '-', '2', '+', '-3', '+', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '-', '-3', '-', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '-', '-3', '-', '1', '+', '-1']
['3', '-', '5', '-', '-7', '+', '2', '-', '-3', '+', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '-', '-3', '+', '1', '+', '-1']
['3', '-', '5', '-', '-7', '+', '2', '+', '-3', '-', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '+', '-3', '-', '1', '+', '-1']
['3', '-', '5', '-', '-7', '+', '2', '+', '-3', '+', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '+', '-3', '+', '1', '+', '-1']
['3', '+', '5', '-', '-7', '-', '2', '-', '-3', '-', '1', '-', '-1']
['3', '+', '5', '-', '-7', '-', '2', '-', '-3', '-', '1', '+', '-1']
['3', '+', '5', '-', '-7', '-', '2', '-', '-3', '+', '1', '-', '-1']
['3', '+', '5', '-', '-7', '-', '2', '-', '-3', '+', '1', '+', '-1']
['3', '+', '5', '-', '-7', '-', '2', '+', '-3', '-', '1', '-', '-1']
['3', '+', '5', '-', '-7', '-', '2', '+', '-3', '-', '1', '+', '-1']
['3', '+', '5', '-', '-7', '-', '2', '+', '-3', '+', '1', '-', '-1']
['3', '+', '5', '-', '-7', '-', '2', '+', '-3', '+', '1', '+', '-1']
['3', '+', '5', '-', '-7', '+', '2', '-', '-3', '-', '1', '-', '-1']
['3', '+', '5', '-', '-7', '+', '2', '-', '-3', '-', '1', '+', '-1']
['3', '+', '5', '-', '-7', '+', '2', '-', '-3', '+', '1', '-', '-1']
['3', '+', '5', '-', '-7', '+', '2', '-', '-3', '+', '1', '+', '-1']
['3', '+', '5', '-', '-7', '+', '2', '+', '-3', '-', '1', '-', '-1']
['3', '+', '5', '-', '-7', '+', '2', '+', '-3', '-', '1', '+', '-1']
['3', '+', '5', '-', '-7', '+', '2', '+', '-3', '+', '1', '-', '-1']
['3', '+', '5', '-', '-7', '+', '2', '+', '-3', '+', '1', '+', '-1']
['3', '+', '5', '+', '-7', '-', '2', '-', '-3', '-', '1', '-', '-1']
['3', '+', '5', '+', '-7', '-', '2', '-', '-3', '+', '1', '-', '-1']
['3', '+', '5', '+', '-7', '-', '2', '-', '-3', '+', '1', '+', '-1']
['3', '+', '5', '+', '-7', '+', '2', '-', '-3', '-', '1', '-', '-1']
['3', '+', '5', '+', '-7', '+', '2', '-', '-3', '-', '1', '+', '-1']
['3', '+', '5', '+', '-7', '+', '2', '-', '-3', '+', '1', '-', '-1']
['3', '+', '5', '+', '-7', '+', '2', '-', '-3', '+', '1', '+', '-1']
['3', '+', '5', '+', '-7', '+', '2', '+', '-3', '+', '1', '-', '-1']
Searches through binary tree of (+/-) using a function search.
预先计算数组中每个索引到末尾的绝对值之和，允许在搜索中终止于中间节点。
这是因为如果到目前为止的值之和 + 从当前索引到数组末尾的值的累计值 < 0，那么我们知道剩余数组中没有足够的值来克服当前的负累加值。
def findsums(a, n = -1, sumsofar = 0, signs = [], results = [], cumsum = []):
"""
finds additions and subtraction of array element which are >= 0
a - input array\n
n - highest index element of array we\'re using on the previous iteration
sumsofar - sum using element up to index
signs - signs (+/-) applied to these eleemnt
results - solutions
cumsum - cumulative sum of elements from index i to the end of array
"""
if not cumsum:
# Base case getting started
#
# Cumulative so of a in reverse order
cumsum = cumsum_calc(a)
# Use the first number as-is (i.e. no +/- sign)
signs = [''] # first element is a
sumsofar = a[0]
n = 0
# terminal case
if n >= len(a)-1:
if sumsofar >= 0:
# terminal case (valid solution, so add)
results.append(signs[:])
else:
# invalid solution
pass # nothing to do
elif n == -1 or sumsofar + cumsum[n] >= 0:
# Viable candidate so far
# Try +/- alternatives\n
# Try + sign
signs.append(' + ')
findsums(a, n+1, sumsofar+a[n+1], signs, results, cumsum)
signs.pop()
# Try '-' sign
signs.append(' - ')
findsums(a, n+1, sumsofar-a[n+1], signs, results, cumsum)
signs.pop()
else:
# Backtrack (sumsofar + cumsum[n] < 0):
# No valid solution going forward\n
# So don\'t go any further with this sequence
pass
return results
def cumsum_calc(arr):
" accum sum from next index forward in the array "
# Adepted from https://www.geeksforgeeks.org/python-program-to-find-cumulative-sum-of-a-list/\n
# maximum sum of elements after i
b = [abs(x) for x in arr]
return [sum(b[i+1:]) for i in range(len(b)+1)]
def show_solutions(a, signs):
" intertwines signs and array to show how they are added "
# convert a to string, with parentheses around negative values
converta = list(map(str, a))
# place sign before each value in array a (converta)
# function to generate list of sign, value pairs
create_sign_value_pairs = lambda sign: list(zip(sign, converta))
# Create sign/value pairs (i.e. [[('+', '(-1)'), ('+', '2')],...]
sol_with_signs = list(map(create_sign_value_pairs, signs))
# Convert each solution to a string
solutions = list(map(lambda sol: ' '.join([''.join(s) for s in sol]), sol_with_signs))
return "\t" + '\n\t'.join(solutions)
tests = [[2, 3], [-1, 2], [1], [-1], [-1, -2], [1, 2, 3, 4, -5]]
示例用法
测试 = [[2, 3], [-1, 2], [1], [-1], [-1, -2], [1, 2, 3, 4, -5] ]
测试中的 t： s = findsums(t, 结果 = []) 打印（"For array {}, solutions are:".格式（t）） 打印（show_solutions（t，s））
输出
For array [2, 3], solutions are:
2 + 3
For array [-1, 2], solutions are:
-1 + 2
For array [1], solutions are:
1
For array [-1], solutions are:
For array [-1, -2], solutions are:
-1 - -2
For array [1, 2, 3, 4, -5], solutions are:
1 + 2 + 3 + 4 + -5
1 + 2 + 3 + 4 - -5
1 + 2 + 3 - 4 - -5
1 + 2 - 3 + 4 - -5
1 + 2 - 3 - 4 - -5
1 - 2 + 3 + 4 + -5
1 - 2 + 3 + 4 - -5
1 - 2 + 3 - 4 - -5
1 - 2 - 3 + 4 - -5
性能
有：arr = [-1, 1, 2, 3, 3, 1,3, 34,2,1,2,-4, -9, 2, 11]
使用 Grzegorz Skibinski（组合方法）
760 ms ± 12.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
当前方法（使用回溯）
72.1 ms ± 2.34 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
使用回溯比测试所有组合快 10 倍