【Day 72 】2023-04-26 - 78. 子集

[azl397985856]

78. 子集

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/subsets/

前置知识

• 位运算
• 回溯

  题目描述

  
  给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

 

示例 1：

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

输入：nums = [0] 输出：[[],[0]]  

提示：

1 <= nums.length <= 10 -10 <= nums[i] <= 10 nums 中的所有元素 互不相同

[Zoeyzyzyzy]

class Solution {
    //TC: O(n*2^n) SC: O(n)
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        backtracking(0);
        return res;
    }

    private void backtracking(int startIndex) {
        res.add(new ArrayList<>(path));
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            backtracking(i + 1);
            path.remove(path.size() - 1);
        }
    }
}

[RestlessBreeze]

code

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

    void backtrack(vector<int>& nums, int startindex)
    {
        res.push_back(path);
        if (startindex >= nums.size())
        { 
            return;
        }
        for (int i = startindex; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            backtrack(nums, i + 1);
            path.pop_back();
        }
    }

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

[LIMBO42]

class Solution {
public:
    vector<vector<int>> ans;
    void dfs(int index, vector<int> &vec, vector<int> &nums) {
        if(index >= nums.size()) {
            ans.push_back(vec);
            return;
        }
        // for(int i = index)
        dfs(index+1, vec, nums);
        vec.push_back(nums[index]);
        dfs(index+1, vec, nums);
        vec.pop_back();
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> vec;
        dfs(0, vec, nums);
        return ans;
    }
};

[NorthSeacoder]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const res = [];
    const path = [];
    const backtracking = (index) => {
        res.push([...path]);
        for (let i = index; i < nums.length; i++) {
            path.push(nums[i]);
            backtracking(i + 1);
            path.pop();
        }
    };
    backtracking(0, []);
    return res;
};

[bookyue]

TC: O(2^n)
SC: O(n)

    public List<List<Integer>> subsets(int[] nums) {
        return dfs(nums, 0, new ArrayDeque<>(), new ArrayList<>());
    }

    private List<List<Integer>> dfs(int[] nums, int idx, Deque<Integer> subset, List<List<Integer>> res) {
        res.add(new ArrayList<>(subset));

        for (int i = idx; i < nums.length; i++) {
            subset.addLast(nums[i]);
            dfs(nums, i + 1, subset, res);
            subset.removeLast();
        }

        return res;
    }

[jackgaoyuan]

func subsets(nums []int) [][]int {
    var res [][]int
    var curSet []int
    recursive(nums, &curSet, 0, &res)
    return res
}

func recursive(nums []int, curSet *[]int, index int, res *[][]int) {
    if index > len(nums)-1 {
        dst := make([]int, len(*curSet))
        copy(dst, *curSet)
        *res = append(*res, dst)
        return
    }
    // not add current element to curSet
    recursive(nums, curSet, index+1, res)
    // add current element to curSet
    *curSet = append(*curSet, nums[index])
    recursive(nums, curSet, index+1, res)
    *curSet = (*curSet)[0 : len(*curSet)-1]
}

[chocolate-emperor]

class Solution {
public:
    //dfs回溯，f(n-1)所有的子集+ 第n号元素选 或 不选
    vector<vector<int>>res;
    void dfs(vector<int>&nums,int index,unordered_map<int,int>&isExist){
        if(index == nums.size()){
            vector<int>tmp;
            for(auto i:nums){
                if(isExist[i]==1)  tmp.emplace_back(i);
            }
            res.emplace_back(tmp);
            return;
        }

        isExist[nums[index]] = 1;
        dfs(nums,index+1,isExist);
        isExist[nums[index]] = 0;
        dfs(nums,index+1,isExist);
        //dfs(nums,i+1,tmp);
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        unordered_map<int,int>isExist;
        dfs(nums,0,isExist);
        return res;
    }
};

[Diana21170648]

思路

位运算

from typing import List
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res,end=[],1<<len(nums)
        n=len(nums)
        for sign in range(end):
            subset=[]
            for i in range(n):
                if ((1<<i)&sign) !=0:#用于判断整数的二进制的某一位是否为1
                   subset.append(nums[i])
            res.append(subset)
        return res
Solution().subsets( [1,2,3])

**复杂度分析**
- 时间复杂度：O(N*2^N)，其中 N 为数组长度。
- 空间复杂度：O(N)

[Abby-xu]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ret = []
        self.dfs(nums, [], ret)
        return ret

    def dfs(self, nums, path, ret):
        ret.append(path)
        for i in range(len(nums)):
            self.dfs(nums[i+1:], path+[nums[i]], ret)

[huizsh]

class Solution {

    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> res = new LinkedList<>();

        int start = 0, end = 1 << nums.length;

        for (int sign = start; sign < end; sign++) {

            List<Integer> list = new LinkedList<>();

            for (int i = 0; i < nums.length; i++)
                if (((1 << i) & sign) != 0)
                    list.add(nums[i]);

            res.add(list);
        }

        return res;
    }
}

[linlizzz]

class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res, end = [], 1 << len(nums)
        for sign in range(end):
            subset = []
            for i in range(len(nums)):
                if ((1 << i) & sign) != 0:
                    subset.append(nums[i])
            res.append(subset)
        return res

[FireHaoSky]

思路：位运算

代码：python

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        size = len(nums)
        n = 1 << size
        res = []
        for i in range(n):
            cur = []
            for j in range(size):
                if i >> j & 1:
                    cur.append(nums[j])
            res.append(cur)
        return res

复杂度分析：

"""
时间复杂度：O(n*size)
空间复杂度：O(n)
"""

[csthaha]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const res = [];
    const backTrack = (path, index) => {
        if(index === nums.length) {
            res.push([...path]);
            return;
        }
        path.push(nums[index]) // 当前元素选择
        backTrack(path, index + 1);
        path.pop();   // 当前元素不选择。
        backTrack(path, index + 1)
    }
    backTrack([], 0)
    return res;
};

[kofzhang]

思路

DFS，两种选择，要么扔进去，要么不扔进去。到最后一个的时候添加答案。

复杂度

时间复杂度：O(n*2^n) 空间复杂度：O(n)

代码

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        def dfs(cur,li):
            if cur<len(nums):
                dfs(cur+1,li)
                dfs(cur+1,li+[nums[cur]])
            else:
                res.append(li)
        dfs(0,[])
        return res

[snmyj]

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

[harperz24]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []
        n = len(nums)
        for i in range(1 << n):
            for j in range(n):
                if i & (1 << j):
                    subset.append(nums[j])
            res.append(subset)
            subset = []

        return res

        # time: O(2ⁿ * n)
        # space: O(n)

[Size-of]

var subsets = function(nums) {
  let n = nums.length, list = [[]]

  function backtrack(max, res = [], start = 0) {
    if (max === 0) return list.push([...res])

    for (let i = start; i < n; ++i) {
      res.push(nums[i])
      backtrack(--max, res, i + 1)
      max++
      res.pop()
    }
  }

  for (let i = 1; i <= n; ++i) {
    backtrack(i)
  }

  return list
};

[enrilwang]

class Solution { //TC: O(n*2^n) SC: O(n) List<List> res = new ArrayList<>(); List path = new ArrayList<>(); int[] nums;

public List<List<Integer>> subsets(int[] nums) {
    this.nums = nums;
    backtracking(0);
    return res;
}

private void backtracking(int startIndex) {
    res.add(new ArrayList<>(path));
    for (int i = startIndex; i < nums.length; i++) {
        path.add(nums[i]);
        backtracking(i + 1);
        path.remove(path.size() - 1);
    }
}

}

[JasonQiu]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        for i in range(1 << len(nums)):
            current = []
            for j in range(len(nums)):
                if i >> j & 1:
                    current.append(nums[j])
            result.append(current)
        return result

Time: O(n^2) Space: O(n)

[joemonkeylee]

思路

BackTrack

代码

      IList<IList<int>> Ilist = new List<IList<int>>();
    List<int> list = new List<int>();

    public IList<IList<int>> Subsets(int[] nums) {
        BackTrack(nums, 0);
        return Ilist;
    }

    public void BackTrack(int[] nums, int Idx){
        Ilist.Add(new List<int>(list));
        if(Idx >= nums.Length)       
            return;

        for(int i = Idx; i < nums.Length; i++)
        {
            list.Add(nums[i]);
            BackTrack(nums, i + 1);
            list.RemoveAt(list.Count - 1);
        }
    }

[Jetery]

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

[Fuku-L]

代码

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        int start = 0, end = 1 << nums.length;
        for(int sign = start; sign < end; sign++){
            List<Integer> list = new LinkedList<>();
            for(int i = 0; i<nums.length; i++){
                if(((1<<i) & sign) != 0){
                    list.add(nums[i]);
                }
            }
                res.add(list);
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(N*2^N)，其中 N 为数组长度。
• 空间复杂度：O(N)

[lp1506947671]

class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res, end = [], 1 << len(nums)
        for sign in range(end):
            subset = []
            for i in range(len(nums)):
                if ((1 << i) & sign) != 0:
                    subset.append(nums[i])
            res.append(subset)
        return res

复杂度分析

令 N 为数组长度

• 时间复杂度：O(N*2^N)

[X1AOX1A]

class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res, end = [], 1 << len(nums)
        for sign in range(end):
            subset = []
            for i in range(len(nums)):
                if ((1 << i) & sign) != 0:
                    subset.append(nums[i])
            res.append(subset)
        return res

[yingchehu]

class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res, end = [], 1 << len(nums)
        for sign in range(end):
            subset = []
            for i in range(len(nums)):
                if ((1 << i) & sign) != 0:
                    subset.append(nums[i])
            res.append(subset)
        return res

[aoxiangw]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []
        def dfs(i):
            if i >= len(nums):
                res.append(subset.copy())
                return
            subset.append(nums[i])
            dfs(i + 1)
            subset.pop()
            dfs(i + 1)

        dfs(0)
        return res

[Lydia61]

78. 子集

思路

python 库函数

代码

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        for i in range(len(nums)+1):
            for tmp in itertools.combinations(nums, i):
                res.append(tmp)
        return res

复杂度分析

• 时间复杂度：O(n*2^n)
• 空间复杂度：O(n)

[chanceyliu]

代码

function subsets(nums: number[]): number[][] {
  const ans: number[][] = [];
  const n = nums.length;
  for (let mask = 0; mask < 1 << n; ++mask) {
    const t: number[] = [];
    for (let i = 0; i < n; ++i) {
      if (mask & (1 << i)) {
        t.push(nums[i]);
      }
    }
    ans.push(t);
  }
  return ans;
}

[kangliqi1]

class Solution { List<List> res = new ArrayList<>(); List path = new ArrayList<>(); int[] nums;

public List<List<Integer>> subsets(int[] nums) {
    this.nums = nums;
    backtracking(0);
    return res;
}

private void backtracking(int startIndex) {
    res.add(new ArrayList<>(path));
    for (int i = startIndex; i < nums.length; i++) {
        path.add(nums[i]);
        backtracking(i + 1);
        path.remove(path.size() - 1);
    }
}

}