Checking if you can divide list into 2 with exact sum of numbers that are in them

Question

My problem is that I have a list, for example

l =[1, 2, 3, 4, 5, 15]

and I would like to divide it in two lists, list1 that would have a single element of the actual list which should be the sum of all other numbers in the list, and list2 containing rest. So the output for this would be ([1, 2, 3, 4, 5], [15]) if its possible if not, return False.

Answer 1

This is one way, though not necessarily optimal. It uses the, in my opinion underused, for...else... construct.

I've also reversed the range iterator. This is more efficient in the case you provided.

l = [1, 2, 3, 4, 5, 15]

def splitter(l):
    for i in reversed(range(len(l))):
        if sum(l[:i]) == sum(l[i:]):
            return [l[:i], l[i:]]
    else:
        return False

splitter(l)  # [[1, 2, 3, 4, 5], [15]]

Answer 2

Should it be possible for the positions of the values to change in the list? If not you can try an iteration such as:

l = [1, 2, 3, 4, 5, 15]
dividable = "False"
x = 0

while dividable == "False":
    l1 = l[0:x]
    l2 = l[x:len(l)]
    if sum(l1) == sum(l2):
        dividable = "True"
    elif x == len(l):
        #not possible
        break
    else:
        x += 1

Answer 3

This answer should help in all cases. No imports required and no sorting required for the data.

def split_list(l):
     dividable=False
     index=0
     for i in range(len(l)):
         if l[i]==sum(l)-l[i]:
             dividable=True
             index=i
             break
     if dividable:
         l1=l[index]
         l.remove(l[index])
         return (l1,l)
     else:
         return False

Might not be the optimised way, but a better and clear way to understand for beginners.

split_list([1,2,3,4,5,15])

[15],[1,2,3,4,5]

Hope this helps. Thanks

Answer 4

what about this?

l =[1, 2, 3, 4, 5, 15]
l=sorted(l)
track=[]
for i in l:
    track.append(i)
    if sum(track) in l and len(track)==len(l[1:]):
        print(track,[sum(track)])

output:

[1, 2, 3, 4, 5], [15]

Answer 5

You need to do a couple of steps:

1) Sort the list from small to large. (Into a new list if you don't want to alter the original)

2) Sum every other element of the list and see if it's equal.

3) If false return false

4) if true:

Store the last (biggest) value in a variable and delete this from the duplicate of the original list.

Make a second list with only that last value in it.

Create another new list and add the altered duplicate list and the list made of the biggest element.

Return the last created list.

Then you're done

Answer 6

Using numpy:

def split(l):
    c = np.cumsum(l)
    idx = np.flatnonzero(np.equal(l, c[-1] / 2.0))
    return (l[:idx[0]], l[idx[0]:]) if idx.size > 0 else False

Alternatively, if using Python > 3.2:

import itertools
def split(l):
    c = list(itertools.accumulate(l))
    h = c[-1] / 2.0
    if h in c:
        i = l.index(h)
        return l[:i], l[i:]
    return False

Finally, if you want to use "pure" Python (no imports):

def split(l):
    c = [sum(l[:k]) for k in range(1, len(l) + 1)]
    h = c[-1] / 2.0
    if h in c:
        i = l.index(h)
        return l[:i], l[i:]
    return False

Answer 7

Brute force:

import itertools

x = [1, 2, 3, 4, 5, 15]

for size in range(1,len(x)):
    for sublist in itertools.combinations(x, size):
        comp = x[:]
        for n in sublist:
            comp.remove(n)

        if sum(comp) == sum(sublist):
            print(comp, sublist)

[1, 2, 3, 4, 5] (15,)
[15] (1, 2, 3, 4, 5)

This approach can handle duplicated numbers.