当前位置：首页 > news >正文

LeetCode 面试题 08.04. 幂集

news 2025/7/21 20:06:58

文章目录

一、题目
二、C# 题解

一、题目

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

说明：

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

示例:

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

点击此处跳转题目。

二、C# 题解

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

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

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

${ { } } Sub(\{0\})=\{\{\}\}$
$Sub(\{0,1\})=\{\{\}\}\cup\{\{\bold{1}\}\}=\{\{\},\{1\}\}$
$Sub(\{0,1,2\})=\{\{\},\{1\}\}\cup\{\{\bold{2}\},\{1,\bold{2}\}\}=\{\{\},\{1\},\{2\},\{1,2\}\}$
$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\}\}$

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;}
}