Find two disjoint susequences with minimum difference( > n)

Question

You are given an array of positive numbers and you need to find two disjoint sub sequences with minimum difference less than or equal to n. These sub sequences may or may not be contiguous

For Example 

if array = [10,12,101,105,1000] and n = 10
Ans = [10,105] & [12,101]

If minimum difference > n then there is no solution.

Ex- array = [100, 150, 125] and n = 7

I assume this could be done using DP but I fail to derive a recurrence.

Answer 1

If the sum of all your elements is not too big (within millions), then you can do a solution similar to a knapsack problem. Your DP state is a difference between two sets, and for every element you iterate over all the differences you know so far, and update them. Since a difference cannot exceed the sum of all the elements, the complexity ends up being O(n * s) where n is the number of elements and s is their sum. You will need some kind of logic to restore the answer. For example, if all your elements are non-negative, you can just store the previous difference. Here's an example python code (I slightly modified your sample case, because for your case it finds a non-interesting answer [10], [12])

a = [5, 20, 30, 1000]
n = 7

states = {(0, False, False): None} # state is sum, hasPositive, hasNegative => prevsum, prevHasP, prevHasN
for el in a:
    newStates = {}

    for k, v in states.items():
        newStates[k] = v

    for v, hasP, hasN in states:
        if (v + el, True, hasN) not in newStates:
            newStates[(v + el, True, hasN)] = (v, hasP, hasN)
        if (v - el, hasP, True) not in newStates:
            newStates[(v - el, hasP, True)] = (v, hasP, hasN)

    states = newStates

best = None
for key, hasP, hasN in states.keys():
    if key >= -n and key <= n and hasP and hasN and (best == None or abs(best[0]) > abs(key)):
        best = (key, hasP, hasN)

if best is None: print "Impossible"
else:
    ans1 = []
    ans2 = []
    while best[1] or best[2]: # while hasPositive or hasNegative
        prev = states[best]

        delta = best[0] - prev[0]
        if delta > 0:
            ans1.append(delta)
        else:
            ans2.append(- delta)

        best = prev

    print ans1
    print ans2

As I mentioned before, it will only work if all your elements are non-negative, but it is easy to adjust the code that restores the answer to also work if the elements can be negative.