子集

发表于 | 分类于 | 阅读次数：
本文字数： 2k | 阅读时长 ≈ 5 分钟

问题提出

#78 子集

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

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
> 输入: nums = [1,2,3]
> 输出:
> [
>   [3],
>   [1],
>   [2],
>   [1,2,3],
>   [1,3],
>   [2,3],
>   [1,2],
>   []
> ]
>

解法

假设已知n个元素的集合的全部子集，多加一个元素，其全部子集会变成什么样？

设之前的集合为{a1, a2}，则全部子集为{Φ, {a1}, {a2}, {a1, a2}}，加入a3后，保留之前的全部子集外，需要在之前的每个子集的后面加上a3并入新的全部子集的集合，即{Φ, {a1}, {a2}, {a1, a2}} ∪ { {a3}, {a1, a3}, {a2, a3}, {a1, a2, a3}}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<int>> subsets(vector<int>& nums) {
    int len = nums.size();
    vector<vector<int>> ret;
    vector<int> vec;
    ret.push_back(vec);
    if (len == 0) {
        return ret;
    }

    for (int i = 0; i < len; i++) {
        int size = ret.size();
        for (int j = 0; j < size; j++) {
            ret.push_back(ret[j]);
            ret.back().push_back(nums[i]);
        }
    }
    return ret;
}

另解

还有一种很巧妙的利用二叉树的递归算法，示例二叉树如下：

1
2
3
4
5
6
7
8
9
10
11

                      []        
                    /    \        
                  /        \     
               /             \
            [1]               []
          /     \            /   \
        /        \          /     \        
     [1 2]       [1]       [2]     []
    /     \     /   \     /   \    / \
[1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []

其中第 i 列添加上第 i 个元素，二叉树在分叉时，有两种选择，可以添加新元素，也可以保持不变，最终的叶子节点即为所求。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int> > subsets(vector<int> &S) {
    vector<vector<int> > res;
    vector<int> out;
    sort(S.begin(), S.end());
    getSubsets(S, 0, out, res);
    return res;
}
void getSubsets(vector<int> &S, int pos, vector<int> &out, vector<vector<int> > &res) {
    res.push_back(out);
    for (int i = pos; i < S.size(); ++i) {
        out.push_back(S[i]);
        getSubsets(S, i + 1, out, res);
        out.pop_back();
    }
}

参考文章