Given an array of n numbers find all the ways of inserting + and - between them so that the result of the expression is positive.
I've found this problem recently and I thought it was interesting, but I'm not exactly sure how to solve it. I think I should try backtracking, no? Any help or hints are deeply appreciated!
Edit: Would this be a correct solution? (I wrote it in 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)
My thought process was that there are n-1 gaps between those numbers. Each gap can have a '+' or a '-' in it. And so I build a list where list[i] is equal with 0 if between array[i] and array[i+1] there is an "-", and list[i] is equal with 0 if between array[i] and array[i+1] there is an "+". And I generated all the possible ways of choosing the values in the list, then I checked if that possible candidate is consistent or not. And I said that if the partial sum (calculated using the + and - in our current list) added to the maximum sum of the remaining elements of the given array is a negative number, then the candidate is inconsistent. If the candidate is consistent and it has the required length, then I said that it is a solution.
For example, if I had the array "array = [1,2,3,4,5,6,7]" as input, I was given the following solutions:
[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]
Backtracking is indeed a reasonable strategy. Since you need to enumerate, there's only one pruning trick that makes an asymptotic difference. Suppose that the array starts with a very large negative number, e.g.,
−50 10 10 10 10 1 2 3 4 5
The sum always includes a −50 term, so the sign for each 10 must be positive since otherwise the remaining numbers aren't large enough to make the overall sum positive. By making the example bigger (more and bigger numbers), we can create an exponential gap between the complexity of naive backtracking and the number of solutions.
If we implement the usual depth-first backtracking strategy and maintain the sum of the absolute values of the remaining array elements, then we can prune every node where the partial sum plus the sum of absolute values is not positive. Since every node not pruned yields at least one solution, we end up with an optimal output-sensitive time complexity.