Problem 56368. Find a subset that divides the vector into equal halves --- HARD MODE

Christian Schröder

4 solvers

0 likes

Solve

Solve Later

This problem is the same as Ned Gulley's problem 660, but the input arrays will be larger.
As in problem 660, given a vector x, return the indices of elements of x that sum to half the sum of x, i.e. return a vector xi such that isequal(sum(x(xi))*2, sum(x)). If there's several solutions, all of them are valid, and the elements of xi do not have to be in any particular order. All that is required is that x(xi) sums to the correct value.
For instance, when
x = [ 2     3     5     7    11    13    17    19    23 ]
your function could (but doesn't have to) return
xi = [ 6     7     1     4     5 ]
since sum(x) = 100, and sum(x(xi)) = 13 + 17 + 2 + 7 + 11 = 50. Your function should work for larger input vectors and finish in a reasonable amount of time. You may assume that sum(x) is even.
Note: the test suite won't check for hacks, cheats and other unsportsmanlike behavior. Please show good sportsmanship, and solve the actual problem.