算法技能树——子集

一、题目

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
输入：nums = [0]
输出：[[],[0]]

提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

二、解题

2.1 一般解

新值与前面集合再组合， 就按下图的方式进行子集的生成

python

def subsets(nums):
    if not nums:
        return []
    res = [[]]
    # 当前数与前面的集合全部组合
    for i in range(len(nums)):
        print('--'*15)
        n_res = len(res)
        for j in range(n_res):
            tmp = [i for i in res[j]]
            print(f'[numIdx: {i} - resIdx: {j}] {tmp} + {nums[i]}', end = '\t')
            tmp.append(nums[i])
            print(f' => {tmp}')
            res.append(tmp)
    print('--'*15)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

cpp

class Solution
{
public:
    vector<vector<int>> subsets(vector<int> &nums)
    {
        vector<vector<int>> res;
        if (nums.empty())
            return res;
        res.push_back({});
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {


            int nRes = res.size();
            for (int j = 0; j < nRes; j++)
            {
                vector<int> temp = res[j];
                temp.push_back(nums[i]);
                res.push_back(temp);
            }
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2.2 二进制解

其实不重复的排列组合就是 $1-2^{len(list)}$，所以只需要遍历$1-2^{len(list)}$， 然后与位置代表的值（1 << idx）取并，就可以拿到我们需要的子集。

python

def subsets_bin(nums):
    # 1 << num_len 个组合 
    # 0 ~ bin(num_len) 正好是对应位置的组合
    num_len = len(nums)
    num_cnt = 1 << num_len
    res = []
    i = 0
    while i < num_cnt:
        print('--'*7, bin(i)[2:].zfill(num_len), '--'*7)
        tmp = []
        for n in range(num_len):
            # 确定是需要的位置
            if (1 << n) & i:
                print(f"n={n}, 1<{1<<n}, judge={(1 << n) & i} | append")
                tmp.append(nums[n])
                continue
            print(f"n={n}, 1<{1<<n}, judge={(1 << n) & i}")
        print(f'tmp: {tmp}')
        i += 1
        res.append(tmp)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

cpp

class Solution
{
public:
    vector<vector<int>> subsets(vector<int> &nums)
    {
        int numssize = nums.size();
        int numscount = 1 << numssize;
        vector<vector<int>> output;
        int i = 0;
        while (i < numscount)
        {
            vector<int> newtemp;
            for (int x = 0; x < numssize; x++)
            {
                if ((1 << x) & i)
                {
                    newtemp.push_back(nums[x]);
                }
            }
            i++;
            output.push_back(newtemp);
        }
        return output;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25