回溯算法--子集
输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
注意点：
- 组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
- 那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！
代码
根据回溯三部曲
参数、终止条件、单层递归逻辑，写出代码
代码
#include<iostream> #include<vector> using namespace std; class Solution { private: vector<vector<int>> result; // 存储所有子集的结果集 vector<int> path; // 存储当前正在构建的子集（路径） // 回溯函数：生成所有子集 // nums: 输入的数字数组 // startIndex: 当前递归开始选择的起始索引（避免重复选择） void backtracking(const vector<int>& nums, int startIndex){ // 终止条件1：当当前路径长度等于原数组长度时 // 说明已构建了一个包含所有元素的子集（即原数组本身） if(path.size() == nums.size()){ result.push_back(path); // 将完整子集加入结果 return; // 结束当前递归分支 } // 关键点：每次进入递归都先将当前path加入结果 // 这样能收集所有中间状态的子集，包括空集、部分子集 result.push_back(path); // 遍历所有可能的选择：从startIndex开始到数组末尾 for(int i = startIndex; i < nums.size(); i ++){ path.push_back(nums[i]); // 做选择：将当前数字加入路径 backtracking(nums, i + 1); // 递归：以i+1为起始点继续构建子集 path.pop_back(); // 撤销选择：回溯，移除最后加入的数字 } } public: vector<vector<int>> subsets(vector<int>& nums) { result.clear(); // 清空结果集，避免之前的数据干扰 path.clear(); // 清空当前路径 backtracking(nums, 0); // 从索引0开始回溯 return result; // 返回所有子集 } }; int main(){ Solution S; vector<int> nums = {1, 2, 3, 4}; vector<vector<int>> res = S.subsets(nums); for(auto row : res){ // 遍历每个组合 for(auto cols : row) // 遍历组合中的每个数字 cout << cols << " " ; // 输出数字 cout << endl; // 每个组合后换行 } return 0; }