# 子集

题目链接🔗

如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

子集也是一种组合问题，因为它的集合是无序的，子集 {1,2} 和子集 {2,1} 是一样的。

Alt text

遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。

全局变量数组 path 为子集收集元素，二维数组 result 存放子集组合。

用 startIndex 保证元素不会重复取。

剩余集合为空的时候，就是叶子节点。就是 startIndex 已经大于数组的长度了，就终止了。

可以不需要加终止条件，因为 startIndex >= nums.size ()，本层 for 循环本来也结束了。

因为要遍历整棵树，找所有的节点，因此子集问题不需要剪枝。

	class Solution {
	private:
	vector<vector<int>> result;
	vector<int> path;
	void backtracking(vector<int>& nums, int startIndex) {
	result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
	if (startIndex >= nums.size()) return;
	for (int i = startIndex; i < nums.size(); i++) {
	path.push_back(nums[i]);
	backtracking(nums, i + 1);
	path.pop_back();
	}
	}
	public:
	vector<vector<int>> subsets(vector<int>& nums) {
	result.clear();
	path.clear();
	backtracking(nums, 0);
	return result;
	}
	};

# 子集 II

题目链接🔗

和上一题的区别在于有重复元素了，要求子集去重。

先对集合排序，然后和组合总数II 的思路一样，用 used [] 数组或者 startIndex 去重。

Alt text

用 used [] 数组去重版本。

	class Solution {
	private:
	vector<vector<int>> result;
	vector<int> path;
	void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
	result.push_back(path);
	for (int i = startIndex; i < nums.size(); i++) {
	//used [i - 1] == true，说明同一树枝 candidates [i - 1] 使用过
	//used [i - 1] == false，说明同一树层 candidates [i - 1] 使用过
	// 而我们要对同一树层使用过的元素进行跳过
	if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
	continue;
	}
	path.push_back(nums[i]);
	used[i] = true;
	backtracking(nums, i + 1, used);
	used[i] = false;
	path.pop_back();
	}
	}

	public:
	vector<vector<int>> subsetsWithDup(vector<int>& nums) {
	result.clear();
	path.clear();
	vector<bool> used(nums.size(), false);
	sort(nums.begin(), nums.end()); // 去重需要排序
	backtracking(nums, 0, used);
	return result;
	}
	};

startIndex 去重版本。

	class Solution {
	private:
	vector<vector<int>> result;
	vector<int> path;
	void backtracking(vector<int>& nums, int startIndex) {
	result.push_back(path);
	for (int i = startIndex; i < nums.size(); i++) {
	// 而我们要对同一树层使用过的元素进行跳过
	if (i > startIndex && nums[i] == nums[i - 1] ) { // 注意这里使用 i > startIndex
	continue;
	}
	path.push_back(nums[i]);
	backtracking(nums, i + 1);
	path.pop_back();
	}
	}

	public:
	vector<vector<int>> subsetsWithDup(vector<int>& nums) {
	result.clear();
	path.clear();
	sort(nums.begin(), nums.end()); // 去重需要排序
	backtracking(nums, 0);
	return result;
	}
	};

题目链接🔗

不能对原数组排序，因为排完序后都是递增子序列了，所以不能用之前的去重逻辑。

以 [4, 7, 6 ,7] 举例：

Alt text

和之前一样，定义全局变量 path 和 result。

另外本题求子序列，很明显元素不能重复使用，需要 startIndex 调整下一层起始位置。

题目要求子序列大小至少为 2，所以当 $path.size() > 1$ 时就将结果添加进 result。

在图中可以看出，同一父节点下的同层上使用过的元素就不能再使用了。

可以用 set 来对本层的元素进行去重。

	class Solution {
	private:
	vector<vector<int>> result;
	vector<int> path;
	void backtracking(vector<int>& nums, int startIndex) {
	if (path.size() > 1) {
	result.push_back(path);
	// 注意这里不要加 return，要取树上的节点
	}
	unordered_set<int> uset; // 控制某一节点下的同一层元素不能重复
	for (int i = startIndex; i < nums.size(); i++) {
	if ((!path.empty() && nums[i] < path.back())
	\|\| uset.find(nums[i]) != uset.end()) {
	continue;
	}
	uset.insert(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了
	path.push_back(nums[i]);
	backtracking(nums, i + 1);
	path.pop_back();
	}
	}
	public:
	vector<vector<int>> findSubsequences(vector<int>& nums) {
	result.clear();
	path.clear();
	backtracking(nums, 0);
	return result;
	}
	};

uset 是记录本层元素是否重复使用，新的一层 uset 都会重新定义（清空）。