leetcode筆記：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],
  []
]

二. 題目分析

該題的大意是，給定一個集合，求出這個集合所有的子集(所謂子集，就是包含原集合中的一部分元素的集合)。可使用DFS遞歸嵌套。總共N層，時間復雜度為O(2^N)。我的做法是使用位運算，一個含有N個元素的數組有2^N個子集，因此該題目可轉換為求數組的元素組合。使用一個N位二進制位表示數組nums的各下標出現與否，當某一位為1表示這次組合中出現當前下標所對應的元素，否則表示不選擇當前下標元素，時間復雜度也是O(2^N)。

三. 示例代碼

// 方法一，位運算
class Solution {
public:
    vector> subsets(vector& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int MAX = 1 << n;
        vector> result;
        for (int i = 0; i < MAX; ++i)
        {
            vector temp;
            int index = 0;
            int j = i;
            while (j > 0)
            {
                if (j & 1) // 二進制數的最低位為1，表示該位出現在此次排列中
                    temp.push_back(nums[index]);
                j = j >> 1; // 一次次移位，判斷各位上是否為1
                ++index;    // nums的下標逐次加1
            }
            result.push_back(temp);
        }
        return result;
    }
};

// 方法二，DFS
#include 
#include 
#include 

using namespace std;

class Solution {
public:
    vector > result;
    vector temp;
    vector> subsets(vector& nums) {
        if(nums.empty()) return result;
        sort(nums.begin(), nums.end());
        dfs(0, temp, nums);
        return result;

    }

private:
    void dfs(int k, vector temp, vector nums){
        result.push_back(temp);
        for(int i = k; i < nums.size(); ++i){
            temp.push_back(nums[i]);
            dfs(i + 1, temp, nums);
            temp.pop_back();
        }
    }
};

四. 小結

就提交結果來看，似乎還有更快的算法。