LeetCode No.78 Subsets

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

Note: The solution set must not contain duplicate subsets.

For example,

If nums = 

[1,2,3]

, a solution is:

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

===================================================================

題目連結：https://leetcode.com/problems/subsets/

題目大意：求出給定集合的所有子集。

思路：深搜（dfs）或寬搜（bfs）。

參考代碼：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size() ;
        sort ( nums.begin() , nums.end() ) ;
        vector <int> temp ;
        vector < vector <int> > ans ( 1 , temp ) ;
        queue < vector <int> > q ;
        q.push ( temp ) ;
        while ( ! q.empty() )
        {
            temp = q.front() ;
            q.pop() ;
            for ( int i = 0 ; i < n ; i ++ )
            {
                if ( temp.empty() || nums[i] > temp.back() )
                {
                    vector <int> tt = temp ;
                    tt.push_back ( nums[i] ) ;
                    ans.push_back ( tt ) ;
                    q.push ( tt ) ;
                }
            }
        }
        return ans ;
    }
};