LeetCode 78. Subsets

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 78. Subsets 原题链接中等

作者：

yxc , 2018-05-01 01:23:28 , 所有人可见 , 阅读 4780

19

5

题目描述

给定一个集合，包含互不相同的数，返回它的所有子集（幂集）。

注意；结果不能包含相同子集。

样例

输入：nums = [1,2,3]
输出：
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

算法

(集合的二进制表示) $O(2^nn)$

假设集合大小是 $n$ ，我们枚举 $0 … 2^n-1$ ，一共 $2^n$ 个数。
每个数表示一个子集，假设这个数的二进制表示的第 $i$ 位是1，则表示该子集包含第 $i$ 个数，否则表示不包含。

另外，如果 $n \ge 30$ ，则 $2^n \ge 10^9$ ，肯定会超时，所以我们可以断定 $n \le 30$ ，可以用int型变量来枚举。

时间复杂度分析：一共枚举 $2^n$ 个数，每个数枚举 $n$ 位，所以总时间复杂度是 $O(2^nn)$ 。

C++ 代码

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        for (int i = 0; i < (1 << n); i ++ )
        {
            vector<int> temp;
            for (int j = 0; j < n; j ++ )
                if (i >> j & 1)
                    temp.push_back(nums[j]);
            res.push_back(temp);
        }
        return res;
    }
};

8 评论

KillLemon 2021-01-10 19:40


class Solution {
public:
    int n;
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> subsets(vector<int>& nums) {
        //采用递归的写法，如果每次看是否选择当前数，如果选择则为一种方案，不选为另外一种方案
        n = nums.size();
        dfs(nums, path, 0);
        return res;
    }

    void dfs(vector<int>& nums,vector<int>& path,int u){
        if(u == n){
            res.push_back(path);
            return;
        }

        path.push_back(nums[u]);
        dfs(nums, path, u + 1);
        path.pop_back();
        dfs(nums, path, u + 1);
    }
};

KillLemon 2021-01-10 19:40

y总在视频里提了一下但是没有写的递归写法

刘晓昱 2021-02-06 17:42

为什么两次dfs

飞飞爱编程 2021-04-02 18:08 回复了刘晓昱的评论

一次是选这个点，一次是不选这个点

Lena 2022-09-20 12:44 回复了刘晓昱的评论

我觉得不需要两次dfs

class Solution {
public:
    vector<bool> flag;
    vector<vector<int>> ans;
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        flag = vector<bool>(n, false);
        vector<int> v;
        dfs(nums, 0, v);
        return ans;
    }

    void dfs(vector<int>& nums, int u, vector<int>& v){

        if(v.size() <= nums.size()){
            ans.push_back(v);
        }

        for(int i = u; i < nums.size(); i++){
            if(flag[i] == false){
                flag[i] = true;
                v.push_back(nums[i]);  
                dfs(nums, i + 1, v);
                v.pop_back();
                flag[i] = false;
            }      
        }
    }
};

xju_wzp 2023-03-31 23:09

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int>& nums, int u) {
        res.push_back(path); // 收集子集，要放在终止条件的上面，否则会漏掉自己
        if (nums.size() == u) return; // 终止条件可以不加

        for (int i = u; i < nums.size(); i++) {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }
};