78. 子集

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 292 阅读时长 ≈ 1 分钟

考点

  • 状态压缩
  • 排列组合

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
	public:
		vector<vector<int>> subsets(vector<int>& nums) {
			vector<vector<int>> ans;
			int size = nums.size();
			for (int i = 0; i < (1 << size); i++) {
				vector<int> tmp;
				for (int j = 0; j < size; j++) {
                    //可以发现，二进制比特位的分布规律都是对称的
                    //假设有数组{1,2,3}，此时i = 1, j = 0
                    //理应代表子集{3}，但也可以用子集{1}替换
					if (i & (1 << j)) tmp.push_back(nums[j]);
				}
				ans.push_back(tmp);
			}
			return ans;
		}
};

时间复杂度：\(O\left( 2^n\cdot n \right)\)

空间复杂度：\(O\left( n \right)\)

思路

题目已经表明，数组中的元素互不相同，故而不会产生重复的子集

数组中的每个元素都有取与不取两种状态，使用比特位1代表取状态、比特位0代表不取状态

若nums数组长度为n，按照数学的组合规律则共有2n个子集，可以用\(\left[ 0,2^n-1 \right]\)范围内的十进制整数来表达

假设有数组{1,2,3}，子集表达如下：

十进制表达 二进制表达 子集
0 000 {}
1 001 {3}
2 010 {2}
3 011 {2,3}
4 100 {1}
5 101 {1,3}
6 110 {1,2}
7 111 {1,2,3}