子集

🟡 中等

题目描述

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

解法一

参考答案 (2 个标签)

回溯 O(2^n)

思路

每个元素都有选或不选两种可能，通过 start 参数避免重复。

代码实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function subsets(nums) {
    const result = [];
    
    function backtrack(start, path) {
        result.push([...path]);
        
        for (let i = start; i < nums.length; i++) {
            path.push(nums[i]);
            backtrack(i + 1, path);
            path.pop();
        }
    }
    
    backtrack(0, []);
    return result;
}

复杂度分析

时间复杂度：O(n × 2^n)，共有 2^n 个子集
空间复杂度：O(n)，递归深度

解法二

参考答案 (2 个标签)

迭代 O(2^n)

思路

遍历每个元素，将其加入所有已有子集中形成新子集。

代码实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function subsets(nums) {
    const result = [[]];
    
    for (const num of nums) {
        const n = result.length;
        for (let i = 0; i < n; i++) {
            result.push([...result[i], num]);
        }
    }
    
    return result;
}

图解

nums = [1, 2, 3]

初始: [[]]
加入 1: [[], [1]]
加入 2: [[], [1], [2], [1, 2]]
加入 3: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

上一章节全排列

下一章节组合总和