子集生成算法

本文介绍生成一个集合子集的两种常见算法，借此从中深入理解搜索问题中常见的两种思路。

递归回溯

思路

对于集合中的每个元素，我们都有选择和不选择两种处理方式，这种思路类似于二叉树的遍历，每种情况都向下衍生出两种情况，最终当遍历到下标 index = nums.size() 时，将生成的子集保存。

由于此处我们使用一个数组的引用来保存子集元素，因此在递归回溯时，我们需要手动将上一步中加入添加的元素去除，来回溯到该元素未被选择的状态。

代码

class Solution {
private:
	std::vector<std::vector<int>> Sets;
	void search(std::vector<int>& subset, std::vector<int>& nums, int index) {
		if (index == nums.size()) {
			Sets.emplace_back(subset);
			return;
		}
		subset.emplace_back(nums[index]);
		search(subset, nums, index + 1);
		subset.pop_back();
		search(subset, nums, index + 1);
	}
public:
	std::vector<std::vector<int>> getSubset(std::vector<int>& nums) {
		std::vector<int> subset;
		search(subset, nums, 0);
		return Sets;
	}
};

状态压缩

思路

我们知道，一个集合的非空子集个数为 2ⁿ - 1，因此可以将子集状态表示为一个范围在 [1, 2ⁿ] 的二进制数。

二进制数位 ai 若为 0，表示第 i 位未被选中；若为 1，表示第 i 位被选中。而要分析一个压缩的状态，即获取表示该状态二进制数各位的值，可以运用位运算的操作。由于一个二进制数和 1 进行按位与（&）操作得到的结果将只由该数的最低位决定，如果最低位为 0，则运算结果为 0，否则为 1. 由此可以想到，将一个状态数依次右移 n 位得到一个以 an 结尾的二进制数，再将该二进制数和 1 进行按位与得到 an 的值。依次遍历所有的右移步数得到该状态的所有信息。

代码

class Solution {
private:
	std::vector<std::vector<int>> Sets;
public:
	std::vector<std::vector<int>> getSubset(std::vector<int>& nums) {
		int n = nums.size();
		std::vector<int> subset;
		for (int i = 1; i <= (1 << n); ++i) {
			subset.clear();
			for (int j = 0; j < n; ++j) {
				int isChoosed = i >> j & 1;
				if (isChoosed)
					subset.emplace_back(nums[j]);
			}
			Sets.emplace_back(subset);
		}
		return Sets;
	}
};