How to retrieve subset in partitioning algorithm?
<p>I have an array and I would like to split it two parts such that their sum is equal for example <code>[10, 30, 20, 50]</code> can be split into <code>[10, 40] , [20, 30]</code>. Both have a sum of 50. This is essentially partitioning algorithm but I'd like the retrieve the subsets not just identify whether it's partitionable. So, I went ahead and did the following:</p>

<p><strong>Update</strong>: updated script to handle duplicates</p>

<pre><code>from collections import Counter

def is_partitionable(a):
    possible_sums = [a[0]]
    corresponding_subsets = [[a[0]]]
    target_value = sum(a)/2
    if a[0] == target_value:
        print("yes",[a[0]],a[1:])
        return
    for x in a[1:]:
        temp_possible_sums = []
        for (ind, t) in enumerate(possible_sums):
            cursum = t + x
            if cursum &lt; target_value:
                corresponding_subsets.append(corresponding_subsets[ind] + [x])
                temp_possible_sums.append(cursum)
            if cursum == target_value:
                one_subset = corresponding_subsets[ind] + [x]
                another_subset = list((Counter(a) - Counter(one_subset)).elements())
                print("yes", one_subset,another_subset)
                return
        possible_sums.extend(temp_possible_sums)
    print("no")
    return

is_partitionable(list(map(int, input().split())))
</code></pre>

<p>Sample Input &amp; Output:</p>

<pre><code>&gt;&gt;&gt; is_partitionable([10,30,20,40])
yes [10, 40] [30, 20]
&gt;&gt;&gt; is_partitionable([10,30,20,20])
yes [10, 30] [20, 20]
&gt;&gt;&gt; is_partitionable([10,30,20,10])
no
</code></pre>

<p>I'm essentially storing the corresponding values that were added to get a value in <code>corresponding_subsets</code>. But, as the size of <code>a</code> increases, it's obvious that the <code>corresponding_subsets</code> would have way too many sub-lists (equal to the number of elements in <code>possible_sums</code>). Is there a better/more efficient way to do this?</p>

<p>This is my implementation of @sasha's algo on the feasibility.</p>

<pre><code>def my_part(my_list):
    item = my_list.pop()
    balance = []
    temp = [item, -item]
    while len(my_list) != 0:
        new_player = my_list.pop()
        for i, items in enumerate(temp):
            balance.append(items + new_player)
            balance.append(items - new_player)
        temp = balance[:]
    balance = set(balance)
    if 0 in balance:
        return 'YES'
    else:
        return 'NO'
</code></pre>

<p>I am working on the backtracking too.</p>

python algorithm performance python-3.x partitioning