给定一个包含 n 个数字的数组，找到在它们之间插入“+”和“-”的所有方式，使得表达式的结果为正

Question

给定一个包含 n 个数字的数组，找到在它们之间插入 + 和 - 的所有方法，使得表达式的结果为正数。

我最近发现了这个问题，我觉得它很有趣，但我不确定如何解决它。我想我应该尝试回溯，不是吗？非常感谢任何帮助或提示！

编辑：这是正确的解决方案吗？（我写在python）


def outputSolution(list):
    print(list)

def solution(x, dim):
    return len(x) == dim-1

def consistent(list, array):
    partial_sum = array[0]
    for i in range(len(list)):
        if list[i] == 0:
            partial_sum = partial_sum - array[i+1]
        if list[i] == 1:
            partial_sum = partial_sum + array[i+1]
            
    absolute_remaining_sum = 0
    for i in range(len(list)+1, len(array)): #the remaining elements in array
        absolute_remaining_sum =absolute_remaining_sum + abs(array[i])
        
    if partial_sum + absolute_remaining_sum < 0:
        return False
    else:
        return True
            
    

def solve(list, array):
    """
    array - the array of n given integers
    list -  the candidate to a solution
    """
    
    dim = len(array)
    
    for el in range(2): # el = 0 or 1 (0 for - and 1 for +)
        if len(list) < dim - 1:
            list.append(el)
            if consistent(list, array):
                if solution(list, dim):
                    outputSolution(list)
                solve(list[:], array)
            list.pop()

        
solve([], array)

我的思考过程是这些数字之间有 n-1 个差距。每个间隙中都可以有一个“+”或“-”。所以我构建了一个列表，其中如果 array[i] 和 array[i+1] 之间有一个“-”，list[i] 等于 0，如果 array[i] 之间有 list[i] 等于 0和 array[i+1] 有一个“+”。我生成了选择列表中值的所有可能方式，然后我检查了那个可能的候选者是否一致。而我说如果给定数组剩余元素的最大和加上的部分和（用我们当前列表中的+和-计算）是负数，那么候选不一致。如果候选一致，并且有要求的长度，那我就说是解

例如，如果我将数组“array = [1,2,3,4,5,6,7]”作为输入，我得到以下解决方案：

[0, 0, 0, 1, 1, 1]
[0, 0, 1, 0, 1, 1]
[0, 0, 1, 1, 0, 1]
[0, 0, 1, 1, 1, 0]
[0, 0, 1, 1, 1, 1]
[0, 1, 0, 0, 1, 1]
[0, 1, 0, 1, 0, 1]
[0, 1, 0, 1, 1, 0]
[0, 1, 0, 1, 1, 1]
[0, 1, 1, 0, 0, 1]
[0, 1, 1, 0, 1, 0]
[0, 1, 1, 0, 1, 1]
[0, 1, 1, 1, 0, 1]
[0, 1, 1, 1, 1, 0]
[0, 1, 1, 1, 1, 1]
[1, 0, 0, 0, 1, 1]
[1, 0, 0, 1, 0, 1]
[1, 0, 0, 1, 1, 0]
[1, 0, 0, 1, 1, 1]
[1, 0, 1, 0, 0, 1]
[1, 0, 1, 0, 1, 1]
[1, 0, 1, 1, 0, 1]
[1, 0, 1, 1, 1, 0]
[1, 0, 1, 1, 1, 1]
[1, 1, 0, 0, 1, 1]
[1, 1, 0, 1, 0, 1]
[1, 1, 0, 1, 1, 0]
[1, 1, 0, 1, 1, 1]
[1, 1, 1, 0, 0, 1]
[1, 1, 1, 0, 1, 0]
[1, 1, 1, 0, 1, 1]
[1, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 1, 1]

Answer 1

回溯确实是一个合理的策略。由于您需要枚举，因此只有一种修剪技巧可以产生渐近差异。假设数组以一个非常大的负数开始，例如，

−50 10 10 10 10 1 2 3 4 5

总和始终包含 −50 项，因此每 10 项的符号必须为正，否则剩余数字不足以使总和为正。通过使示例更大（越来越多的数字），我们可以在朴素回溯的复杂性和解决方案的数量之间形成指数差距。

如果我们采用通常的深度优先回溯策略，保持剩余数组元素的绝对值之和，那么我们就可以剪掉每一个部分和加上绝对值之和不为正的节点。由于每个未修剪的节点都至少产生一个解决方案，因此我们最终得到了最佳的输出敏感时间复杂度。

给定一个包含 n 个数字的数组，找到在它们之间插入“+”和“-”的所有方式，使得表达式的结果为正

Given an array of n numbers find all the ways of inserting "+" and "-" between them so that the result of the expression is positive

algorithm

backtracking