## Sunday, January 6, 2013

### [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],
[]
]
```
» Solve this problem

[解题思路]

Func Generate

选取该字符到子集合中，并输出
如果，当前字符不是最后一位字符
递归调用Generate,处理下一位字符

[Code]
``````1:    vector<vector<int> > subsets(vector<int> &S) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      vector<vector<int> > result;
5:      vector<int> output;
6:      if(S.size() ==0) return result;
7:      result.push_back(output);
8:      sort(S.begin(), S.end());
9:      generateSub(S, 0, result, output);
10:    }
11:    void generateSub(
12:      vector<int> &s,
13:      int step,
14:      vector<vector<int> > &result,
15:      vector<int>& output)
16:    {
17:      for(int i = step;i<s.size(); i++ )
18:      {
19:        output.push_back(s[i]);
20:        result.push_back(output);
21:        if(i< s.size()-1)
22:          generateSub(s, i+1, result, output);
23:        output.pop_back();
24:      }
25:    }
``````