题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解题思路

我们可以使用经典的回溯法解题模板，来求解这个问题：

相关代码如下：

class Solution:
    def subsets(self, nums):
        result = []

        def recursive(select, allnums):
            if select not in result:
                result.append(select.copy())
            for i, num in enumerate(allnums):
                select.append(num)
                recursive(select, allnums[i + 1:])
                select.remove(num)

        recursive([], nums)
        return result

这种经典的回溯解法当然是万能的，但是时间复杂度稍微有点高。我们在这里来介绍一种新的方法。

迭代法实现子集枚举

记原序列中元素的总数为 n。原序列中的每个数字 a_i的状态可能有两种，即「在子集中」和「不在子集中」。我们用 1 表示「在子集中」，0 表示不在子集中，那么每一个子集可以对应一个长度为 n 的 0/1序列，第 i 位表示 a_i是否在子集中。例如，n = 3 ，a = { 5, 2, 9 } 时：

0/1 序列	子集	0/10/1 序列对应的二进制数
000	{ }	0
001	{ 9 }	1
010	{ 2 }	2
011	{ 2, 9 }	3
100	{ 5 }	4
101	{ 5, 9 }	5
110	{ 5, 2 }	6
111	{ 5, 2, 9 }	7

可以发现 0/1序列对应的二进制数正好从 0 到 2^n - 1。我们可以枚举 mask∈[0,2^n−1]，mask 的二进制表示是一个 0/1序列，我们可以按照这个 0/1序列在原集合当中取数。当我们枚举完所有 2^n个 mask，我们也就能构造出所有的子集。

代码实现

class Solution:
    def subsets(self, nums):
        result = []
        n = len(nums)
        for mask in range(1<<n):
            select = []
            for i in range(n):
                if mask & 1<<i != 0:
                    select.append(nums[i])
            result.append(select)
        return result

class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}

参考文献

https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode-solution/