(每日算法)LeetCode --- Subsets(子集合)

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

  For example,
  If S = [1,2,3], a solution is:

  [
    [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
  ]
  

  Show Tags
  

  
  

  
  

  子集合，还是通过回溯的方法来求解。跟之前k个元素的自己不一样的是这里任意个子元素都可以作为子集合。因此有子集合的时候我们都希望能够添加到solution中，可以通过空迭代的方式添加。还有就是先添加一个元素，来调用sub函数，然后回溯，就是把刚添加的元素去除。因为在调用sub的过程中还有分支的过程，这是足够的。

  
  

  <??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHByZSBjbGFzcz0="brush:java;">class Solution { public: void sub(vector & s, int index, vector & path, vector >& solution) { if(s.size() == index) { solution.push_back(path); return; } sub(s, index + 1, path, solution); path.push_back(s[index]); sub(s, index + 1, path, solution); path.pop_back(); } vector > subsets(vector &S) { vector > solution; vector path; sort(S.begin(), S.end()); sub(S, 0, path, solution); return solution; } };