如何return一个整数列表的所有子集的列表，使用Python？

Question

我得到了一个整数数组 A，我需要 return 它所有子集的数组。我已经尝试使用回溯来解决这个问题。

def subset_helper(index, result, A, temp):
    result.append(temp)
    #print(temp)
    for i in range(index,len(A)):
        temp.append(A[i])
        subset_helper(i+1,result,A,temp)
        #backtracking
        temp.pop()
    return    
def subsets(A):
    result = []
    temp = []
    index = 0
    subset_helper(index, result, A, temp)
    return result

这 return 给我一个空列表。打印温度给了我正确的答案，但问题要求我 return 一个数组。我猜由于 引用调用 导致的临时数组在每次迭代中都会发生变化，这可能是它给我空列表列表的原因。

Input : [12,13]
Expected Output : [[],[12],[12,13],[13]]
My Output : [[],[],[],[]]

Answer 1

您可以使用 powerset 来获得您正在寻找的输出。

iterable=[12,13]
res=list(powerset(iterable))

Answer 2

你可以尝试在subset_helper中打印地址，你可以发现你的temp是同一个对象地址，这就是为什么您的结果是相同对象值的列表：

def subset_helper(index, result, A, temp):
    result.append(temp)
    print(id(temp))
    for i in range(index,len(A)):
        temp.append(A[i])
        subset_helper(i+1,result,A,temp)
        #backtracking
        temp.pop()
    return

输出：

1559293711304
1559293711304
1559293711304
1559293711304
[[], [], [], []]

现在，更改以附加 tmp 对象的副本：

import copy
def subset_helper(index, result, A, temp):
    result.append(copy.copy(temp))
    for i in range(index,len(A)):
        temp.append(A[i])
        subset_helper(i+1,result,A,temp)
        #backtracking
        temp.pop()
    return

现在您将一个新对象附加到结果列表，您可以看到预期的输出：

[[], [12], [12, 13], [13]]

Answer 3

如果不是作业问题，可以使用优秀的itertools模块生成子集

from itertools import combinations, chain

def get_subsets(integers):
    return list(chain.from_iterable([combinations(integers, i) for i in range(len(integers) + 1)]))

Input: get_subsets([1, 2, 3])
Output: [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Answer 4

另外，从算法的角度，你可以遍历所有可能的二进制数，直到2**N（N是你的集合的长度），取1表示该元素应该属于子集：

A = ["A", "B", "C"]

allSubsets = []
for i in range(2**len(A)):
  n = 1
  subset = []
  for j in range(len(A)):
    if i & n != 0:
      subset.append(A[j])
    n <<= 1
  allSubsets.append(subset)

print(allSubsets)

产生：

[[], ['A'], ['B'], ['A', 'B'], ['C'], ['A', 'C'], ['B', 'C'], ['A', 'B', 'C']]

如何return一个整数列表的所有子集的列表，使用Python？

How to return the list of all the Subset of a list of integer, using Python?

python

pass-by-reference

backtracking