LeetCode78:Subsets

Given a set of distinct integers, nums, 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 nums = [1,2,3], a solution is:

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

這道題可以使用兩種方法求解，一是使用位操作，另外是使用深度優先搜索和回溯，但是我只想出了位操作，深度優先的方法是看了Discuss後想出來的。

解法一：位操作

對於數組[1,2,3]，可以用一個下標0和1表示是否選擇該數字，0表示未選擇，1表示選中，那麼每一組3個0和1的組合表示一種選擇，3位共有8種選擇，分別是：
000 對應[]
001 對應[3]
010 對應[2]
011 對應[2,3]
100 …
101
110
111
那麼上面為1的位表示數組中該位被選中。
那麼只需要遍歷0到1<< length中的數，判斷每一個數中有那幾位為1，為1的那幾位即會構成一個子集中的一個元素。

runtime:8ms

class Solution {
public:
    vector> subsets(vector& nums) {
        int length=nums.size();
        sort(nums.begin(),nums.end());
        vector > result;
        for(int i=0;i<1< tmp;
            //計算i中有那幾位為1
            for(int j=0;j

解法二：回溯法

還可以使用深度優先搜索來遍歷數組，采用回溯法來剔除元素。使用一個變量來記錄路徑，每遍歷到一個元素即表示找到一條路徑，將其加入子集中。
對於數組[1,2,3]
從1開始遞歸查詢2,3，對於2，繼續向下搜索，搜索完後將2刪除。
runtime:8ms

class Solution {
public:    
    //使用深度優先的回溯法
     vector> subsets(vector& nums) {
         vector> result;
         vector path;
         sort(nums.begin(),nums.end());
         result.push_back(path);
         dfs(nums,0,path,result);
         return result;
     }
     void dfs(vector& nums,int pos,vector & path,vector> & result)
     {
            if(pos==nums.size())
                return;

            for(int i=pos;i