LintCode(17) Subsets

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

Have you met this question in a real interview? 

Yes

Example

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

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

Note

Elements in a subset must be in non-descending order.

The solution set must not contain duplicate subsets.

经典的回溯，没啥好说的，直接贴答案吧。。。看不懂自己画个图就知道了

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public: /** * @param S: A set of numbers. * @return: A list of lists. All valid subsets. */ vector<vector<int> > subsets(vector<int> &nums) { // write your code here vector<vector<int>> result; vector<int> solution; sort(nums.begin(),nums.end()); dfs(nums,result,solution, 0); return result; } void dfs(vector<int>& nums, vector<vector<int>>& result, vector<int>& solution,int ind){ result.push_back(solution); if (solution.size()==nums.size()) return; for (int i=ind; i<nums.size(); i++){ solution.push_back(nums[i]); dfs(nums,result,solution,i+1); solution.pop_back(); } } };