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>Though it is still a hard problem, you could try the following. I assume that there are <code>n</code> elements and they are stored in the array named <code>arr</code> ( I assume 1-based indexing ). Let us make two teams <code>A</code> and <code>B</code>, such that I want to partition the elements of <code>arr</code> among teams <code>A</code> and <code>B</code> such that sum of elements in both the teams is equal. Each element of <code>arr</code> has an option of either going to team <code>A</code> or team <code>B</code>. Say if an element ( say ith element ) goes to team <code>A</code> we denote it by <code>-a[i]</code> and if it goes to team <code>B</code> we let it be <code>a[i]</code>. Thus after assigning each element to a team, if the total sum is <code>0</code> our job is done. We will create <code>n</code> sets ( they do not store duplicates ). I will work with the example <code>arr = {10,20,30,40}</code>. Follow the following steps</p>

<pre><code>set_1 = {10,-10} # -10 if it goes to Team A and 10 if goes to B

set_2 = {30,-10,10,-30} # four options as we add -20 and 20

set_3 = {60,0,20,-40,-20,-60} # note we don't need to store duplicates

set_4 = {100,20,40,-40,60,-20,-80,0,-60,-100} # see there is a zero means our task is possible
</code></pre>

<p>Now all you have to do is backtrack from the <code>0</code> in the last set to see if the ith element <code>a[i]</code> was added as <code>a[i]</code> or as <code>-a[i]</code>, ie. whether it is added to Team <code>A</code> or <code>B</code>.</p>

<p><strong>EDIT</strong></p>

<p>The backtracking routine. So we have <code>n</code> sets from <code>set_1</code> to <code>set_n</code>. Let us make two lists <code>list_A</code> to push the elements that belong to team <code>A</code> and similarly <code>list_B</code>. We start from <code>set_n</code> , thus using a variable <code>current_set</code> initially having value <code>n</code>. Also we are focusing at element <code>0</code> in the last list, thus using a variable <code>current_element</code> initially having value <code>0</code>. Follow the approach in the code below ( I assume all sets 1 to <code>n</code> have been formed, for sake of ease I have stored them as list of list, but you should use set data structure ). Also the code below assumes a <code>0</code> is seen in the last list ie. our task is possible. </p>

<pre><code>sets = [ [0], #see this dummy set it is important, this is set_0
              #because initially we add -arr[0] or arr[0] to 0
         [10,-10],
         [30,-10,10,-30],
         [60,0,20,-40,-20,-60],
         [100,20,40,-40,60,-20,-80,0,-60,-100]]

# my array is 1 based so ignore the zero
arr = [0,10,20,30,40]

list_A = []
list_B = []

current_element = 0
current_set = 4 # Total number of sets in this case is n=4

while current_set &gt;= 1:
   print current_set,current_element
   for element in sets[current_set-1]:
     if element + arr[current_set] == current_element:
       list_B.append(arr[current_set])
       current_element = element
       current_set -= 1
       break
     elif element - arr[current_set] == current_element:
       list_A.append(arr[current_set])
       current_element = element
       current_set -= 1
       break


print list_A,list_B
</code></pre>

python algorithm performance python-3.x partitioning