Lintcode: 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.

Tags Expand 

Recursion

Initial thought:

I imitate the combination problem: 

I resolve this subsets problem into solve combinations problem.

Assume there are n numbers in vector, I can get combinations of k numbers from n

Let k be from 0 to n, and combining all solutions, I will get all subsets.

In below codes, combine () functions works to get combination for different k

Time: O(n! + (n-1)! + (n-2)! + ... + 1)
Space: O(n)

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 27 28 29 30 31 32 33

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> > res; sort(nums.begin(), nums.end()); for(int i = 0; i <= nums.size(); i++){ combine(i, nums, res); } return res; } private: void combine(int n, vector<int> &nums, vector<vector<int> > &res){ vector<int> tempres; DFS(0, n, nums, tempres, res); } void DFS(int start, int n, vector<int> &nums, vector<int> &tempres, vector<vector<int> > &res){ if(n == 0) { res.push_back(tempres); return; } for(int i = start; i < nums.size() - n + 1; i++){ tempres.push_back(nums[i]); DFS(i + 1, n - 1, nums, tempres, res); tempres.pop_back(); } } };

Common solution:
//Reference thoughts and cods
https://siddontang.gitbooks.io/leetcode-solution/content/backtracking/subsets.html


Just push all result in tempres into res when dfs
Time: O(n!)
Space: O(n)

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

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> > res; vector<int> tempres; sort(nums.begin(), nums.end()); res.push_back(tempres); DFS(0, nums, tempres, res); return res; } private: void DFS(int start, vector<int> &nums, vector<int> &tempres,vector<vector<int> > &res){ for(int i = start; i < nums.size(); i++){ tempres.push_back(nums[i]); DFS(i + 1, nums, tempres, res); res.push_back(tempres); tempres.pop_back(); } } };