如何在分区算法中检索子集？

我有一个数组,我想将它分成两部分,例如它们的总和是相等的,例如[10,30,20,50]可以分成[10,40],[20,30].两者都有50的总和.这实际上是分区算法,但我想检索子集不仅仅是确定它是否可分区.所以,我继续做了以下事情：

更新：更新的脚本以处理重复项

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 < 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())))

样本输入&输出：

>>> is_partitionable([10,30,20,40])
yes [10, 40] [30, 20]
>>> is_partitionable([10,30,20,20])
yes [10, 30] [20, 20]
>>> is_partitionable([10,30,20,10])
no

我实际上存储了相应的值,这些值是为了在对应的子集中获取值而添加的.但是,随着a的大小增加,很明显对应的子集将有太多的子列表(等于possible_sums中的元素数量).有没有更好/更有效的方法来做到这一点？

虽然这仍然是一个难题,但您可以尝试以下方法.我假设有n个元素,它们存储在名为arr的数组中(我假设基于1的索引).让我们建立两个A队和B队,这样我就想在A队和B队之间划分arr的元素,这样两支队伍中的元素总和是相等的. arr的每个元素都可以选择进入A队或B队.比如说一个元素(比如ith元素)进入A队,我们用-a [i]来表示它,如果进入B队,我们就让它成为一个[i]中.因此,在将每个元素分配给团队后,如果总和为0,则我们的工作就完成了.我们将创建n个集合(它们不存储重复项).我将使用示例arr = {10,20,30,40}.请执行以下步骤

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

现在你所要做的就是从最后一组中的0回溯,以查看第i个元素a [i]是作为[i]还是作为-a [i]添加,即.是否添加到A队或B队

编辑

回溯例程.所以我们有从set_1到set_n的n个集合.让我们制作两个列表list_A来推送属于团队A的元素和类似的list_B.我们从set_n开始,因此使用最初具有值n的变量current_set.我们也关注最后一个列表中的元素0,因此使用最初具有值0的变量current_element.遵循下面代码中的方法(我假设已经形成了所有集合1到n,为了方便起见,我将它们存储为列表列表,但您应该使用设置数据结构).此外,下面的代码假设在最后一个列表中看到0即ie.我们的任务是可能的.

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 >= 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