Im trying to write code to recursively check if a list could be divided to two sublists with the same sum, so need to pass all the combinations of the list for example: [1,2,3,4] so I need to check:
1------2,3,4
1,2------3,4
1,3------2,4
and so on.... but I cant find the method how to do that.
recursively check if a list could be divided to two sublists with the same sum
You can easily implement the greedy partition algorithm using recursion:
def _greedy_part(r, sa, la, sb, lb):
if not r:
return sa == sb, la, lb;
if sb < sa:
# swap both lists in order to always have
# the "lower sum list" as sa/la
sb, sa = sa, sb
lb, la = la, lb
return _greedy_part(r[1:], sa+r[0], la+r[0:1], sb, lb)
def greedy_part(r):
return _greedy_part(sorted(r,reverse=True), 0, [], 0, [])
The key idea is to always add the greatest remaining value to the list having the lowest sum. Once again, that solution does not perform very well in Python because function calls are not very efficient and Python does not have tail call optimization.
Given that sample tests:
print(greedy_part([1,2,3,4]))
print(greedy_part([1,2,3,4,5]))
print(greedy_part([6,1,2,3]))
It will produce:
(True, [4, 1], [3, 2])
(False, [5, 2, 1], [4, 3])
(True, [3, 2, 1], [6])
Brute force:
import itertools
seq = [1, 2, 3, 4]
S = sum(seq)
for i in xrange(1, len(seq)):
for c in itertools.combinations(seq, i):
print c, 2*sum(c) == S
This is not the most efficient way of solving the problem, though. Read this: http://en.wikipedia.org/wiki/Partition_problem
You can either use
itertools which simleo suggested. This is bruteforce solution and would run in exponential time.
Use traditional subset problem solution given here which runs in (total_sum_of_nums)*len(list) time
