78. 子集

[Geekhyt]

原题链接

回溯

你爱，或者不爱我。爱就在那里，不增不减。

1. 对于数组中的每个元素都有两种选择：选或者不选。
2. 对于当前迭代的元素，选择它就将其 push 后，基于选择后的状态从 start + 1 递归。
3. 然后使用 pop 将其状态恢复，不选择当前迭代的元素从 start + 1 递归。

const subsets = function(nums) => {
    const res = []
    const dfs = function(start, cur) {
        if (start === nums.length) {
            res.push(cur.slice())
            return
        }
        cur.push(nums[start]) // 选择
        dfs(start + 1, cur)
        cur.pop()
        dfs(start + 1, cur) // 不选择
    }
    dfs(0, [])
    return res
}

• 时间复杂度: O(n * 2^n)，共 2^n 个状态，需要 O(n) 的时间来构造子集。
• 空间复杂度: O(n)