两种方式解决子集问题

求集合子集，是回溯算法题中比较经典的题目。类似的题目还有求集合不同的组合等。今天介绍求子集的两种解法。

一、题意分析

题目链接：https://leetcode-cn.com/problems/subsets/

题目重点：

1. 子集，包括空集
2. 题目元素不重复。显然如果是在面试，考虑重复情况会加分
3. 返回结果为 List<list>，集合内元素顺序不固定

二、回溯解法

回溯的基本思想就是先选定一条路，然后一条路走到黑，直到走不了之后，回到上一个选择，选择另一个选项，再一条路直到黑，如此反复，直到所有选项都过一遍。

此外回溯最基本的思想就是递归，优化方式可以考虑通过缓存减少重复计算。通常按照这种思路能解决极大一部分题目，剩下不能 AC 的基本是因为超时，需根据情况进行优化。

直接上代码吧，基于 Pyhton3 实现：

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []

        res = []

        def backtracking(route, choices):
            # 每一次都是一种子集情况，注意需要使用浅拷贝，如果是列表嵌套，则需要深拷贝
            res.append(route[::])
            for i in range(len(choices)):
                # 做出选择
                route.append(choices[i])
                # 递归，对当前做出的选择一条路走到黑
                backtracking(route, choices[i+1::])
                # 当前选择走不下去了，回滚之前的选择
                route.pop()
        backtracking([], nums)
        return res

三、位运算解法

位运算解法则更巧妙，同时也更高效。首先，我们先来想明白一个问题：已经一个集合元素个数为 n ，那它的子集个数是多少？这个问题其实很简单，高中的排列组合问题，n个元素，每个元素可能的情况有两种（出现或不出现），因为总共有 2^n 次方个子集。

想明白这个问题之后，我们再来看，每个元素出现或不出现，是不是对应于二进制中的 0 或 1。以 [1, 2, 3] 的子集为例，我们将 1，2，3 按从右到左的顺序，分别记为第1位，第2位，第3位，第 n 位数值出现在子集里，我们就将这一位记为1，反之记为0，所有情况如下：

• 000 所有元素都不出现，即 []，对应十进制数 0
• 001 第1位元素出现，即 3 出现，所以子集为 [3]，对应十进抽 1
• 010 表示子集 [2]，对应十进制数 2
• 011 表示子集 [2,3]，对应十进制数 3
• 100 表示子集 [1]，对应十进制数 4
• 101 表示子集 [1,3]，对应十进制数 5
• 110 表示子集 [1,2]，对应十进制数 6
• 111 表示子集 [1,2,3]，对应十进制数 7

从上面可以推理我们可以将问题转换为，遍历从 0 到 2^n 的数字，求出该数值对应表示的子集是什么？

这下问题就转换为给你一个数值，怎么求出它对应表示的子集是什么？而对应的子集实际上就是求得哪些位上是 1，一个最基本的思路就是将数值转换为二进制字符串，然后再循环遍历，这个方法可行，但效率明显不高（这里就不实现了）。

另外一种比较巧妙的思路是利用 & 运算，将这个数值分别与 1，10，100 (注意这里是二进制)做 & 运算，如果结果为 1，则表示当前位是1，因为只有 1 & 1 = 1。同样以 [1, 2, 3] 集合为例，如果数值是 5，计算过程应该是这样的：

• 5 & 1 == 110 & 001 = 0，表示第1位上的数值不在子集中
• 5 & 2 == 110 & 010 == 110 & (001 << 1) = 1，表示第2位在子集中
• 5 & 4 == 110 & 100 == 110 & (001 << 2) = 1，表示第3位在子集中
• 因此 5 对应子集为 [1, 2]

这里还有个比较巧的用法，即 << 左移，左移 1 位，即在原数值上乘以2，右移则是除：

1 = 1
2 = 10 = 1 << 1
4 = 100 = 1 << 2

我们来看下代码实现：

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        """基本思路：
        利用二进制：
        比如 [1, 2, 3]，子集的情况应该是 2^3=8 个
        分别对应
        0：表示000，即所有位对应的数字都不出现
        1：表示001，即第1位数出现，则结果对应3，依此类推，直到7
        """
        if not nums:
            return []

        nlen = len(nums)
        result = []
        # 有多少个
        for i in range(0, 1 << nlen):
            # 每个数字对应的子集列表
            result.append([nums[j] for j in range(0, nlen) if (1 << j) & i])
        return result



s = Solution()
print(s.subsets([1, 2, 3]))
print(s.subsets([1, 2, 3, 4, 5, 6]))
print(s.subsets([1, 2, 3]))

三、总结

1. 回溯是基础解法
2. 位运算更巧妙，效率更高，但需要比较熟悉相关操作