Python生成集合所有子集的两种实现方式：递归与二进制法

小满

发布时间：2026-10-13| 6人浏览过

原创

本文介绍Python中生成集合所有子集的两种常用方法。第一种为递归实现，通过分解首元素与剩余列表逐步构建子集；第二种为二进制法，利用位运算枚举2^N种组合。文中提供了完整的Python函数代码，适用于需要遍历子集的场景，如算法测试或组合优化问题。

第一种方法采用递归策略来生成子集。该函数首先检查输入列表是否为空，若为空则直接返回包含空列表的结果。对于非空列表，算法提取第一个元素，并递归处理剩余元素以获取其所有子集。随后，遍历这些子集，将原始子集保留，同时创建包含首元素的新子集并加入结果列表，最终返回完整的子集集合。

def PowerSetsRecursive(items):
  """Use recursive call to return all subsets of items, include empty set"""
  
  if len(items) == 0:
    #if the lsit is empty, return the empty list
    return [[]]
  
  subsets = []
  first_elt = items[0] #first element
  rest_list = items[1:]
  
  #Strategy:Get all subsets of rest_list; for each of those subsets, a full subset list
  #will contain both the original subset as well as a version of the sebset that contains the first_elt
  
  for partial_sebset in PowerSetsRecursive(rest_list):
    subsets.append(partial_sebset)
    next_subset = partial_sebset[:] +[first_elt]
    subsets.append(next_subset)
  return subsets

def PowerSetsRecursive2(items):
  # the power set of the empty set has one element, the empty set
  result = [[]]
  for x in items:
    result.extend([subset + [x] for subset in result])
  return result

第二种方法同样基于递归思想，但实现更为简洁。它初始化一个仅包含空列表的结果集。接着遍历输入列表中的每个元素，对于结果集中已有的每个子集，将其与当前元素组合形成新子集，并扩展至结果列表中。这种方法通过迭代扩展的方式，逐步构建出所有可能的子集组合。

def PowerSetsBinary(items): 
  #generate all combination of N items 
  N = len(items) 
  #enumerate the 2**N possible combinations 
  for i in range(2**N): 
    combo = [] 
    for j in range(N): 
      #test jth bit of integer i 
      if(i >> j ) % 2 == 1: 
        combo.append(items[j]) 
    yield combo

第三种方法利用二进制位运算来生成子集。该方法首先确定集合的大小N，然后遍历从0到2的N次方减1的所有整数。对于每个整数，通过位运算检查其二进制表示中的每一位，若第j位为1，则将集合中对应的第j个元素加入当前组合。通过生成器逐个yield出所有可能的子集组合，从而高效地枚举所有子集。