Medium

题目描述

给你一个整数数组 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 中的所有元素 互不相同

解题思路

解题思路

这道题要求生成一个数组的所有子集，也就是幂集问题。有三种常见的解法：

方法一：回溯法（推荐）

回溯法是最直观的思路。对于每个元素，我们有两种选择：加入当前子集或不加入。通过递归遍历所有可能的选择组合，就能得到所有子集。在递归过程中，我们维护一个当前子集，当遍历完所有元素后，将当前子集加入结果集。

方法二：位操作法

由于子集问题本质上是每个元素选择或不选择的问题，可以用二进制位来表示。对于n个元素，共有2^n个子集，每个子集对应一个从0到2^n-1的二进制数，位为1表示选择该元素，位为0表示不选择。

方法三：迭代法

从空集开始，依次考虑每个元素。对于当前的所有子集，为每个子集创建一个新的子集（在原子集基础上加入当前元素），这样就能逐步构建出所有子集。

回溯法代码清晰易懂，时间复杂度最优，是最推荐的解法。

代码实现

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(nums, 0, current, result);
        return result;
    }
    
private:
    void backtrack(vector<int>& nums, int start, vector<int>& current, vector<vector<int>>& result) {
        result.push_back(current);
        
        for (int i = start; i < nums.size(); i++) {
            current.push_back(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.pop_back();
        }
    }
};

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        
        def backtrack(start, current):
            result.append(current[:])
            
            for i in range(start, len(nums)):
                current.append(nums[i])
                backtrack(i + 1, current)
                current.pop()
        
        backtrack(0, [])
        return result

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        IList<int> current = new List<int>();
        Backtrack(nums, 0, current, result);
        return result;
    }
    
    private void Backtrack(int[] nums, int start, IList<int> current, IList<IList<int>> result) {
        result.Add(new List<int>(current));
        
        for (int i = start; i < nums.Length; i++) {
            current.Add(nums[i]);
            Backtrack(nums, i + 1, current, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

var subsets = function(nums) {
    const result = [];
    
    const backtrack = (start, current) => {
        result.push([...current]);
        
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1, current);
            current.pop();
        }
    };
    
    backtrack(0, []);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(2^n)共有2^n个子集，每个子集需要O(n)时间复制
空间复杂度O(n)递归栈深度为O(n)，不计算结果集的空间

相关题目