本文主要是介绍Leetcode 78 子集 回溯 C++实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Leetcode 78. 子集
问题：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
方法1：
创建返回二维数组 ans ，和临时存储信息的数组 path 。
进入到函数 dfs 中。如果 i==n ，则说明传进来的 nums 数组里的元素都已经递归完毕，则可以 return 。
回溯分为两种情况，选 或者 不选。
如果不选，就直接进入下一个递归（跳过这个元素）；如果选，则把他加入到临时存储信息的数组 path 中，然后进入下一个递归（决定后面的元素选不选），递归完毕后，要删除尾端元素，恢复现场（把这个递归周期中加进 path 中的删掉）。
代码：
class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;// 创建返回数组ansvector<int> path;int n = nums.size();auto dfs = [&](auto&& dfs,int i)->void{if(i == n){ans.emplace_back(path);return ;}// 不选nums[i]dfs(dfs,i+1);// 选nums[i]path.emplace_back(nums[i]);// 把当前数字加入到path后dfs(dfs,i+1);path.pop_back();// 尾端删除元素，恢复现场};dfs(dfs,0);// 入口return ans;}
};时间复杂度：O(n2ⁿ)。
其中 n 为 nums 的长度。每次都是选或不选，递归次数为一个满二叉树的节点个数，那么一共会递归 O(2ⁿ) 次（等比数列和），再算上加入答案时复制 path 需要 O(n) 的时间，所以时间复杂度为 O(n2ⁿ)。
空间复杂度：O(n)。返回值的空间不计。
方法2:
创建返回二维数组 ans ，和临时存储信息的数组 path 。
进入到函数 dfs 中。如果 i==n ，则说明传进来的 nums 数组里的元素都已经递归完毕，则可以 return 。这行代码可以省略，因为当 i==n 时，不会进入循环。
进入到 for 循环中，选元素要从比已经选中的元素大的那些元素中挑选。加入到 path 中，然后进入下一层循环，把 path 加入 ans 中。
代码：
class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;// 创建返回数组ansvector<int> path;int n = nums.size();auto dfs = [&](auto&& dfs,int i)->void{ans.emplace_back(path);// if(i == n) return ;for(int j = i;j < n;j++){// 选从i到n的元素path.emplace_back(nums[j]);// 把当前数字加入到path后dfs(dfs,j + 1);path.pop_back();// 尾端删除元素，恢复现场}};dfs(dfs,0);// 入口return ans;}
};时间复杂度：O(n2ⁿ)。
其中 n 为 nums 的长度。答案的长度为子集的个数，即 2ⁿ，同时每次递归都把一个数组放入答案，因此会递归 2ⁿ次，再算上加入答案时复制 path 需要 O(n) 的时间，所以时间复杂度为 O(n2ⁿ)。
空间复杂度：O(n)。返回值的空间不计。
这篇关于Leetcode 78 子集 回溯 C++实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
