Python 递归实现集合子集问题 - 代码详解

Python 递归实现集合子集问题 - 代码详解

问题分析

子集问题是一个经典的组合问题，给定一个集合，要求输出这个集合的所有子集。子集是指在原集合中选择任意个元素（包括空集和原集合本身）组成的集合。

解题思路分析

可以使用递归的方式来解决子集问题。假设给定的集合为'nums'，递归函数'subset'可以按照以下步骤实现：

1. 初始化一个空集'res'，用于存储所有的子集。
2. 递归的终止条件是当集合'nums'为空时，直接将空集'[]'添加到'res'中，并返回。
3. 递归调用'subset'函数，传入'nums'的子集'nums[1:]'，将返回的所有子集保存在变量'subsets'中。
4. 将'subsets'中的每个子集添加到'res'中，并在每个子集中添加'nums[0]'，形成新的子集，并添加到'res'中。
5. 返回'res'。

完整的代码注释:

def subsets(nums):
    '''
    返回给定集合的所有子集
    :param nums: 给定的集合
    :return: 所有子集的列表
    '''
    res = []  # 用于存储所有的子集

    def subset(nums):
        # 递归的终止条件：当集合为空时，直接将空集添加到res中，并返回
        if len(nums) == 0:
            res.append([])
            return

        # 递归调用subset函数，将返回的所有子集保存在subsets中
        subsets = subset(nums[1:])

        # 将subsets中的每个子集添加到res中，并在每个子集中添加nums[0]，形成新的子集，并添加到res中
        for subset in subsets:
            res.append(subset)
            res.append([nums[0]] + subset)

    subset(nums)  # 调用递归函数

    return res

# 测试
nums = [1, 2, 3]
result = subsets(nums)
print(result)

# 输出: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]