LeetCode 面试题 08.04. 幂集

一、题目

  幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

说明：

• 解集不能包含重复的子集。

示例:

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

  点击此处跳转题目。

二、C# 题解

  记集合为 Q(n)，n 为集合中元素个数（不重复）。Sub(i) 表示集合中 i 个元素组成的所有子集，则有如下递推关系：

$$Sub(i+1)=Sub(i)\cup Sub(i).Add(elem(i+1))$$

其中，$elem(i+1)$ 表示新增加的第 $i+1$ 个元素。以集合 { 1 , 2 , 3 } \{1,2,3\} {1,2,3} 为例：

• S u b ( { 0 } ) = { { } } Sub(\{0\})=\{\{\}\} Sub({0})={{}}
• S u b ( { 0 , 1 } ) = { { } } ∪ { { 1 } } = { { } , { 1 } } Sub(\{0,1\})=\{\{\}\}\cup\{\{\bold{1}\}\}=\{\{\},\{1\}\} Sub({0,1})={{}}∪{{1}}={{},{1}}
• S u b ( { 0 , 1 , 2 } ) = { { } , { 1 } } ∪ { { 2 } , { 1 , 2 } } = { { } , { 1 } , { 2 } , { 1 , 2 } } Sub(\{0,1,2\})=\{\{\},\{1\}\}\cup\{\{\bold{2}\},\{1,\bold{2}\}\}=\{\{\},\{1\},\{2\},\{1,2\}\} Sub({0,1,2})={{},{1}}∪{{2},{1,2}}={{},{1},{2},{1,2}}
• S u b ( { 0 , 1 , 2 , 3 } ) = { { } , { 1 } , { 2 } , { 1 , 2 } } ∪ { { 3 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 } } = { { } , { 1 } , { 2 } , { 3 } , { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 } } Sub(\{0,1,2,3\})=\{\{\},\{1\},\{2\},\{1,2\}\}\cup\{\{\bold{3}\},\{1,\bold{3}\},\{2,\bold{3}\},\{1,2,\bold{3}\}\}=\{\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\} Sub({0,1,2,3})={{},{1},{2},{1,2}}∪{{3},{1,3},{2,3},{1,2,3}}={{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        IList<IList<int>> ans = new List<IList<int>>();
        ans.Add(new List<int>()); // 添加空集
        
        if (nums.Length == 0) return ans;
        
        foreach (int t in nums) {
            int cnt = ans.Count; // 取出原来的长度
            for (int j = 0; j < cnt; j++) {
                // 复制原来所有的子集，将新元素添加进去
                List<int> tmp = new List<int>(ans[j]) { t }; 
                ans.Add(tmp);
            }
        }

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 时间：128 ms，击败 100.00% 使用 C# 的用户
• 内存：40.76 MB，击败 100.00% 使用 C# 的用户