78. 子集

[swiftwind0405]

方法一：回溯法

解题思想：

• 用递归模拟出所有情况
• 保证接的数字都是后面的数字
• 收集所有到达递归终点的情况，并返回

代码：

var subsets = function (nums) {
    const res = [];
    const backtrack = (path, l, start) => {
        if (path.length === l) {
            res.push(path);
            return;
        }
        // for循环遍历数组中的所有数字
        // 没有用forEach来遍历是因为要保证子集的有序性，后面接的数字必须是当前数字后面的数字
        // 因此还需要记录一个下标来
        for (let i = start; i < nums.length; i++) {
            backtrack(path.concat(nums[i]), l, i + 1);
        }
    };
    // 在for循环中进行回溯的调用
    for (let i = 0; i <= nums.length; i++) {
        backtrack([], i, 0);
    }
    return res;
};

复杂度分析：

• 时间复杂度：O(2^N)：因为每个元素都有两种可能（存在或者不存在），全部组合在一起就是2^N；
• 空间复杂度：O(N)：递归的深度。