78. Subsets

Medium

Description

給定一個整數陣列 nums，其中元素互不相同，回傳所有可能的子集（冪集）。結果不能包含重複的子集，可以任意順序回傳。

Example:

Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Intuition#

核心思路：對每個元素做「選或不選」的二元決策，用回溯法遍歷所有決策路徑。

每個元素有兩種選擇：加入子集或不加入
子集問題的搜尋樹：從 index 0 開始，每層決定一個元素的去留
所有葉節點（或所有路徑上的節點）都是合法子集

Approaches#

1: Iterative（逐步擴展）#

概念: 從空集開始，每遇到一個新元素，就在所有現有子集上各加入該元素，產生新的子集
時間複雜度: O(n * 2^n) - 共 2^n 個子集，每個平均長度 O(n)
空間複雜度: O(n * 2^n) - 存放所有子集

class Solution {
    fun subsets(nums: IntArray): List<List<Int>> {
        val result = mutableListOf<List<Int>>(emptyList())

        for (num in nums) {
            val newSubsets = result.map { it + num }
            result.addAll(newSubsets)
        }

        return result
    }
}

⭐2: Backtracking#

概念: 從 index 0 開始，每個位置選擇「加入」或「不加入」，遞迴到底就得到一個子集。用 start index 避免重複
時間複雜度: O(n * 2^n)
空間複雜度: O(n) - 遞迴深度（不計結果空間）

class Solution {
    fun subsets(nums: IntArray): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        val current = mutableListOf<Int>()

        fun backtrack(start: Int) {
            result.add(ArrayList(current))

            for (i in start until nums.size) {
                current.add(nums[i])
                backtrack(i + 1)
                current.removeAt(current.lastIndex)
            }
        }

        backtrack(0)
        return result
    }
}

補充：Bit Manipulation

n 個元素有 2^n 個子集，每個子集可以用一個 n 位元的二進位數表示：第 i 位為 1 代表選了 nums[i]。

class Solution {
    fun subsets(nums: IntArray): List<List<Int>> {
        val n = nums.size
        val result = mutableListOf<List<Int>>()

        for (mask in 0 until (1 shl n)) {
            val subset = mutableListOf<Int>()
            for (i in 0 until n) {
                if (mask and (1 shl i) != 0) {
                    subset.add(nums[i])
                }
            }
            result.add(subset)
        }

        return result
    }
}

時間複雜度: O(n * 2^n)
空間複雜度: O(n) 不計結果

🔑 Takeaways#

Pattern: 子集問題是回溯法的三大基礎之一（子集、組合、排列）
關鍵技巧: 用 start 參數控制只往後選，避免重複子集；每次進入遞迴就收集結果（不需要等到底部）