子集-回溯算法

1题目

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

2链接

题目链接：78. 子集 - 力扣（LeetCode）

视频链接：回溯算法解决子集问题，树上节点都是目标集和！ | LeetCode：78.子集_哔哩哔哩_bilibili

3解题思路

这个题力扣竟然说是中等难度题，我不理解，感觉不难

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

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

那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！

以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下：

 从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。

随手画个图就看出来了，不就需要个startIndex，然后收集所有节点嘛~~

掏出我的回溯三部曲：

1、确定函数参数和返回值

全局变量数组path为子集收集元素，二维数组result存放子集组合。（也可以放到递归函数参数里）。递归函数参数在上面讲到了，需要startIndex。

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {

2、确定终止条件

剩余集合为空的时候，就是叶子节点。

那么什么时候剩余集合为空呢？

就是startIndex已经大于数组的长度了，就终止了，因为没有元素可取了，代码如下:

if (startIndex >= nums.size()) {return;
}

注意startIndex从0开始只能遍历到2，而nums.size() == 3。所以要用 >= 。

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

3、确定单层递归逻辑

求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。

for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);    // 子集收集元素backtracking(nums, i + 1);  // 注意从i+1开始，元素不重复取path.pop_back();            // 回溯
}

4代码

class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path); //result放在这种地方不需要单独处理空集if (startIndex >= nums.size()) return ;for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);// result.push_back(path); //result放这种位置需要单独添加空集backtracking(nums, i + 1);path.pop_back();}return ;}
public:vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums, 0);// result.push_back({}); //单独添加空集return result;}
};