Three Arrays and Subset Sum

Question

Array 1: 1 2 4 8 21

Array 2: 3 5 6 7 19 20

Array 3: 9 10 11 12 13 14 15 16 17 18

There are 3 arrays. We are adding numbers starting from 1. If the number is equal to the sum of any subset, we can not add to it.

For example:

22 can not be added to any array.

Because 1 + 21 = 22, 3 + 19 = 22, 10 + 12 = 22

21 can not be added to array 2.

Because 3 + 5 + 6 + 7 = 21

7 can be added to array 2.

Because (3 + 5 != 7), (3 + 6 != 7), (5 + 6 != 7), (3 + 5 + 6 != 7) ...

Numbers should be added in order. (If I didn't add 22, I can't add 23)

21 is the greatest number what I can add.

I want to add greater number.

Is there a solution for this problem?

What is proper name of this problem?

Thanks...

Answer 1

Using this backtracking solution (it basically checks every possible distribution), we find that 21 is actually the biggest number you can add using 3 arrays. Notice that we are not trying to find the best solution but the maximum number we can add.

def solution(a1, a2, a3, ps1, ps2, ps3, i):
    # First we try to put it on array 1
    m1 = m2 = m3 = 0
    if i not in ps1:
        l = len(ps1)
        ps1.extend([s + i for s in ps1])
        a1.append(i)
        m1 = solution(a1, a2, a3, ps1, ps2, ps3, i+1)
        # Now we backtrack
        a1.pop()
        while(len(ps1) > l):
            ps1.pop()
    if i not in ps2:
        l = len(ps2)
        ps2.extend([s + i for s in ps2])
        a2.append(i)
        m2 = solution(a1, a2, a3, ps1, ps2, ps3, i+1)
        # Now we backtrack
        a2.pop()
        while(len(ps2) > l):
            ps2.pop()
    if i not in ps3:
        l = len(ps3)
        ps3.extend([s + i for s in ps3])
        a3.append(i)
        m3 = solution(a1, a2, a3, ps1, ps2, ps3, i+1)
        # Now we backtrack
        a3.pop()
        while(len(ps3) > l):
            ps3.pop()
    return max(i-1, m1, m2, m3)

Returns 21