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 =
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
对于输入字符串s的每一位字符
选取该字符到子集合中,并输出
如果,当前字符不是最后一位字符
递归调用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: }
No comments:
Post a Comment