【Day 72 】2024-06-18 - 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 中的所有元素 互不相同

[Martina001]

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

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

    private void getZiji(int[] nums,int start,List<Integer> track){
        res.add(new ArrayList<>(track));
        for(int i = start;i<nums.length;i++){
            track.add(nums[i]);
            getZiji(nums,i+1,track);
            track.remove(track.size()-1);
        }
    }

[hillsonziqiu]

思路

我通过递归实现的

代码

/*
 * @lc app=leetcode.cn id=78 lang=javascript
 *
 * [78] 子集
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  const select = [];
  const ans = [];
  const dfs = (index) => {
    if (index === nums.length) {
      ans.push([...select]);
      return;
    }
    select.push(nums[index]);
    dfs(index + 1);
    select.pop();
    dfs(index + 1);
  };
  dfs(0);
  return ans;
};
// @lc code=end

复杂度分析

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

[lxy1108]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        rs = [[]]
        for n in nums:
            tmp = []
            for r in rs:
                tmp.append(r+[n])
            rs+=tmp
        return rs

[zhiyuanpeng]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        for i in range(2**len(nums)):
            cur = []
            for j in range(len(nums)):
                if ((1 << j) & i) != 0:
                    cur.append(nums[j])
            ans.append(cur)
        return ans