子集与幂集
使用回溯和位掩码生成集合的所有子集，通过排序并跳过重复元素来处理重复项。
子集与幂集 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
子集与幂集
集合 S 的幂集是 S 的所有可能子集组成的集合，其中包括空集和 S 本身。包含 n 个元素的集合恰好有2ⁿ个子集。对于 [1, 2, 3]，8 个子集为：[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]。这是一个基础的组合学问题，在面试题中经常出现，例如查找所有可能的组合、划分或选择。
# A set of n elements → 2^n subsets
for n in range(5):
print(f'n={n}: {2**n} subsets')
# n=0: 1 (just the empty set)
# n=1: 2 ([], [x])
# n=2: 4 ([], [a], [b], [a,b])
# n=3: 8 (as enumerated above)
# n=4: 16回溯生成子集
使用选择-探索-撤销选择模板。关键的设计决策是：在每次递归调用中，立即将当前部分路径添加到结果中（在选择更多元素之前）。这样，每个状态——空、部分和完整——都会作为有效子集被记录。推进 start 索引，只考虑位于最后选定元素右侧的元素，从而确保没有重复并保持顺序。
def subsets(nums):
result = []
def backtrack(start, path):
result.append(list(path)) # every state is a valid subset
for i in range(start, len(nums)):
path.append(nums[i]) # CHOOSE
backtrack(i + 1, path) # EXPLORE (advance start)
path.pop() # UNCHOOSE
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]位掩码方法
回溯的另一种方法是位掩码：每个子集对应一个 n 位数字，其中第 i 位为 1 表示包含第 i 个元素。遍历从 0 到 2ⁿ - 1 的数字，并对每个数字提取各位来构建子集。这种方法是迭代式的，实际中通常更快，也很容易编码。不过，对于带约束的问题（例如和的上限），它的推广性不如回溯。
def subsets_bitmask(nums):
n = len(nums)
result = []
for mask in range(1 << n): # 0 to 2^n - 1
subset = []
for i in range(n):
if mask & (1 << i): # bit i is set
subset.append(nums[i])
result.append(subset)
return result
print(subsets_bitmask([1, 2, 3]))
# Same 8 subsets, order may differ迭代生成子集
迭代方法逐个元素构建幂集。从 [[] ]（空集）开始。对于每个新元素，复制所有现有子集，并将新元素追加到每个副本中。处理完 n 个元素后，结果包含全部 2ⁿ 个子集。这与位掩码等价，但对于不熟悉位运算的人来说更易读。
def subsets_iterative(nums):
result = [[]] # start with empty set
for num in nums:
# For each existing subset, create a new subset with num added
result += [subset + [num] for subset in result]
return result
print(subsets_iterative([1, 2, 3]))
# After num=1: [[], [1]]
# After num=2: [[], [1], [2], [1,2]]
# After num=3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]子集 II：处理重复元素
当输入包含重复元素时，朴素方法会生成重复子集。对于 [1, 2, 2]，两个 2 都会独立地产生 [1, 2]。修复方法：先对数组排序，然后如果当前层的候选项等于前一个候选项，就跳过它。具体来说，在循环中：if i > start and nums[i] == nums[i-1]: continue。
def subsets_with_dups(nums):
nums.sort() # sort to group duplicates together
result = []
def backtrack(start, path):
result.append(list(path))
for i in range(start, len(nums)):
# Skip duplicates at the same tree level
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(subsets_with_dups([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]] — no duplicate subsets重复项跳过机制为何有效
条件 i > start and nums[i] == nums[i-1] 只会在同一递归层级（相同的 start）跳过重复项。它不会阻止在不同深度选择相同的值。对于 [1, 2, 2]：在第 0 层，我们包含第一个 2（索引 1），然后在下一层（start=2）包含第二个 2，从而形成 [2, 2]。但如果我们再次尝试在第 0 层包含第二个 2，该条件就会捕获并跳过它。
# Visual: [1, 2, 2] sorted
# Level 0 (start=0): pick nothing, pick 1, pick first-2, pick second-2 (SKIP)
# Level 1 after picking 1 (start=1): pick first-2, pick second-2 (SKIP)
# Level 2 after picking 1,first-2 (start=2): pick second-2
# → [1,2,2] is generated but only once
nums = [1, 2, 2]
nums.sort()
result_set = set(tuple(sorted(s)) for s in subsets_with_dups(nums[:]))
result_naive = set(tuple(sorted(s)) for s in subsets(nums))
print('With dedup:', sorted(result_set))
print('Same results:', result_set == result_naive)
def subsets(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
def subsets_with_dups(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: continue
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
print(len(subsets_with_dups([1,2,2])), 'unique subsets') # 6固定大小的子集（k-组合）
只生成大小恰好为 k 的子集（LeetCode 77：组合）时，需要增加一个提前终止条件：如果剩余元素无法将路径填充到大小 k，就进行剪枝。可剪枝的条件是 i > n - (k - len(path))：如果剩余元素数量不足，就提前停止。与生成所有 subsets 后再筛选相比，这能显著缩小搜索空间。
def combine(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
# Prune: need (k - len(path)) more elements from [start..n]
# At most (n - start + 1) elements remain
if n - start + 1 < k - len(path):
return # not enough elements left
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
print(combine(4, 2)) # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
print(len(combine(10, 3))) # C(10,3) = 120幂集的应用
幂集模式会出现在许多面试题变体中：（1）划分为两个相等的子集——检查是否存在元素和为 total/2 的子集。（2）两个子集的最大 XOR——尝试所有子集对。（3）选择 k 个项目的最小成本——枚举 k-子集。虽然直接枚举具有指数级复杂度，但其中许多问题在识别出结构后都可以使用 DP 解决。即使最终需要对其进行优化，幂集视角也能帮助您确定状态空间。
def max_subset_sum(nums, k):
'''Maximum sum of any k elements (for comparison: O(n log n) alternative)'''
# Backtracking approach: enumerate all k-subsets
max_s = [float('-inf')]
def bt(start, path, curr_sum):
if len(path) == k:
max_s[0] = max(max_s[0], curr_sum)
return
remaining_spots = k - len(path)
for i in range(start, len(nums)):
if len(nums) - i < remaining_spots: break # prune
bt(i+1, path+[nums[i]], curr_sum+nums[i])
bt(0, [], 0)
return max_s[0]
# Much faster: just sort and take top k
def max_subset_sum_fast(nums, k):
return sum(sorted(nums, reverse=True)[:k])
nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(max_subset_sum(nums, 3)) # 20 (9+6+5)
print(max_subset_sum_fast(nums, 3)) # 20子集和检查
子集和要解决的问题是：数组中是否存在某个子集，其元素和等于目标值？这个问题可以通过回溯（指数级复杂度）或 DP（多项式复杂度）解决。回溯版本直观易懂，但输入规模较大时会变得不切实际。DP 版本（布尔表 dp[target+1]）是面试中的首选方法。理解这两种方法有助于您说明其中的权衡：回溯可以给出所有解，而 DP 能够高效地回答判定问题。
# Backtracking version: finds a subset if it exists
def subset_sum_bt(nums, target):
def bt(start, remaining):
if remaining == 0: return True
if remaining < 0 or start == len(nums): return False
# Include nums[start]
if bt(start + 1, remaining - nums[start]): return True
# Exclude nums[start]
return bt(start + 1, remaining)
return bt(0, target)
# DP version: O(n * target) time
def subset_sum_dp(nums, target):
dp = {0}
for num in nums:
dp |= {s + num for s in dp}
return target in dp
print(subset_sum_bt([3, 1, 4, 1, 5], 6)) # True (1+5 or 1+1+4)
print(subset_sum_dp([3, 1, 4, 1, 5], 6)) # True子集枚举的复杂度
生成所有 subsets 的 time 复杂度不可避免地为 O(n × 2ⁿ)——共有 2ⁿ 个子集，每个子集的平均大小为 n/2。当要求返回所有子集时，没有算法能够做得更好。对于只要求寻找具有某种性质的单个子集的问题（例如和最大的子集），应优先考虑 DP 或贪心方法。面试中的关键洞察是：始终先确认您需要枚举所有 subsets，还是只需判断任意子集是否满足条件——答案决定了指数级或多项式 time 是否可以接受。
import time
def count_subsets(n):
nums = list(range(n))
result = []
def bt(start, path):
result.append(None) # count without storing
for i in range(start, len(nums)):
path.append(i); bt(i+1, path); path.pop()
bt(0, [])
return len(result)
for n in [10, 15, 20]:
start = time.time()
cnt = count_subsets(n)
elapsed = time.time() - start
print(f'n={n}: {cnt} subsets ({2**n} expected) in {elapsed:.3f}s')三种方法比较
对于生成所有 subsets：回溯的通用性最强——可以轻松适应重复项和各种约束。位掩码简洁且快速，但受 n ≤ 30（整数大小）的限制。迭代方法直观，并且避免了递归开销。三种方法的输出规模都是 O(n × 2ⁿ)。在面试中，回溯能够体现您对递归决策过程的理解，并且这种理解可以推广到更困难的问题。讨论方法时，请提及这三种方法。
# All three approaches for [1,2,3]
nums = [1, 2, 3]
# 1. Backtracking
def bt(start, path, res):
res.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path, res); path.pop()
res1 = []; bt(0, [], res1)
# 2. Bit masking
res2 = [[nums[i] for i in range(len(nums)) if mask & (1<<i)]
for mask in range(1<<len(nums))]
# 3. Iterative
res3 = [[]]
for num in nums:
res3 += [s+[num] for s in res3]
print('All produce', len(nums)**2, '-ish subsets:',
len(res1), len(res2), len(res3)) # all 8快速检查
请测试您对本课中“数据结构 & 算法——编程面试准备”概念的理解。
课程回顾
本课介绍了：回溯通过在继续探索之前将每条部分路径添加到结果中来生成所有 subsets，重复项通过排序，并使用条件 i > start and nums[i] == nums[i-1] 在相同递归深度跳过重复值来处理，以及位掩码提供了一种简洁的迭代替代方案，其中每个子集都对应一个唯一的位掩码。接下来我们将学习排列和组合——这是约束不同但相关的枚举问题。
常见问题解答
「子集与幂集」课时是免费的吗？
是的 — 「子集与幂集」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「子集与幂集」这节课中我会学到什么？
使用回溯和位掩码生成集合的所有子集，通过排序并跳过重复元素来处理重复项。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「子集与幂集」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。