子集：回溯与枝剪

在求解子集的过程中，常常需要根据不同的情况进行不同的遍历与回溯。

---

求子集，实际上就是一种类似遍历一个集合的所有可能的过程。甚至，在一个简单的求子集问题当中，可以说就是一个遍历所有路径的过程。

因此，求子集的问题，一般可以通过画图的方式来解决。

无需枝剪的子集问题

首先，是一个最基础的子集问题

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

比如，集合[1,2,3],所包含的子集就是[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]],那么，求解的方法很明显就是遍历所有的组合了，这个时候我们可以画图来解决这个问题。

从图中不难看出，从空集出发，不断地根据已选择的元素去递归的选择数组当中的剩余的元素，然后，将每一次的选择的路径保存下来，那么就是子集的内容了。

结合成代码就是这样

vector<vector<int>> subsets(vector<int>& nums) {
       vector<vector<int>> res;      
       vector<int> set;
       allsubsets(nums,res,set,0);
       return res;
   }

   void allsubsets(vector<int>& nums,vector<vector<int>>& result,vector<int>& set, int k)
   {
       result.push_back(set);
       for(int i = k;i < nums.size();i++)
       {

           set.push_back(nums[i]);
           allsubsets(nums,result,set,i + 1);
           set.pop_back();
       }
   }

当然，在递归地遍历地时候，要注意，每一次函数返回之后都要将set的值回溯，因为，set里面所保存的是递归遍历时候的路径，当函数弹出之后，路径自然也要回溯回来了。

然后，将路径保存在结果中，最后也自然能够得到答案了。

题目来源(LeetCode)
链接：https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。