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],
  []
]

二.テーマ分析
この問題の大意は,1つの集合を与えて,この集合のすべてのサブセット(サブセットとは,元の集合の一部の要素を含む集合)を求めることである.DFSを使用して再帰的にネストできます.合計N階建てで、時間の複雑さはO(2^N)です.私のやり方はビット演算を使用して、Nの要素を含む配列に2^Nのサブセットがあるので、このテーマは配列を求める要素の組み合わせに変換することができます.Nビットのバイナリビットを使用して配列numsの各下付き文字が現れるかどうかを表し、あるビットが1である場合、今回の組合せに現在の下付き文字が現れる要素を表し、そうでない場合、現在の下付き文字が選択されないことを示し、時間の複雑さもO(2^N)である.
三.サンプルコード

//    ，   
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int MAX = 1 << n;
        vector<vector<int>> result;
        for (int i = 0; i < MAX; ++i)
        {
            vector<int> 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 <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    }

private:
    void dfs(int k, vector<int> temp, vector<int> 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();
        }
    }
};

四.小結
結果を提出すると、もっと速いアルゴリズムがあるようです.