一、題目介紹
今天要練習的題目是LeetCode 78：Subsets（子集）

題目會給我們一個不包含重複元素的整數陣列nums，需要找出這個陣列所有可能的子集

例如：nums = [1, 2, 3]
所有子集為：
[
[],
[1],
[2],
[3],
[1,2],
[1,3],
[2,3],
[1,2,3]
]

總共有：2³ = 8個子集
其中空集合 [] 也算是一個有效的子集

二、什麼是Subset？
在理解解法之前，可以先理解「子集」的概念

假設：nums = [1, 2]

每個元素都有兩種選擇：

選擇 1
不選擇 1

選擇 2
不選擇 2

因此所有可能性就是：
不選 1、不選 2 → []
選 1、不選 2 → [1]
不選 1、選 2 → [2]
選 1、選 2 → [1,2]

最後得到：
[
[],
[1],
[2],
[1,2]
]

所以如果有 n 個元素，每個元素都有「選」和「不選」兩種可能

因此總共有2ⁿ個子集

三、解題思路：Backtracking
今天的核心是 Backtracking（回溯）
可以把它想成：做一個選擇 → 繼續探索 → 回到上一個狀態 → 換另一個選擇

例如：nums = [1, 2, 3]
從空集合開始：[]
選擇 1：[1]
接著選擇 2：[1,2]
再選擇 3：[1,2,3]
走到底之後，就要回頭撤銷最後一次選擇：

再嘗試其他可能：[1,3]

四、Backtracking的基本架構
這類問題通常可以拆成幾個步驟

1. 建立目前的選擇
2. 將目前結果加入答案
3. 選擇下一個元素
4. 遞迴繼續搜尋
5. 撤銷選擇
6. 嘗試下一個可能

其中最重要的就是：
加入
↓
遞迴
↓
撤銷

例如：
current.add(nums[i]);
backtrack(...);
current.remove(current.size() - 1);

最後這行就是「回溯」

五、Java實作

六、Python實作

七、Java與Python解法比較

八、時間與空間複雜度
假設陣列有n個元素
因為每個元素都有「選擇」和「不選擇」兩種可能，所以總共有：2ⁿ個子集
而每個子集最多需要O(n)的時間來建立或複製

時間複雜度：O(n × 2ⁿ)
空間複雜度：O(n × 2ⁿ)

九、實作結果
Leetcode測試結果：Accepted

十、今日學習心得
今天的Subsets是我第一次比較完整地接觸Backtracking（回溯）。一開始看起來只是要找出陣列的所有子集，但實際思考後，發現每個元素其實都有「選擇」或「不選擇」兩種可能，因此可以利用搜尋樹將所有可能性逐一列舉出來。

在實作過程中，我學到Backtracking最重要的概念就是「選擇、探索、撤銷選擇」。先將元素加入目前的結果，透過遞迴繼續往下一層搜尋，完成後再把最後加入的元素移除，讓程式回到上一個狀態，再嘗試其他可能。

我也了解到start和i + 1的作用，可以限制下一層只能選擇後面的元素，避免產生[1,2]和[2,1]這種其實不需要重複計算的結果。

另外，這題讓我發現 DFS 和 Backtracking 之間有很大的關聯。之前 Day 21、Day 22 使用 DFS 搜尋 Grid，而這次則是利用類似的遞迴搜尋概念，在「選擇的可能性」形成的搜尋樹中探索答案。這讓我開始理解，很多看似不同的演算法，其實背後都建立在相似的搜尋思維上。

今天也更加理解了為什麼 Subsets 會有2ⁿ個結果。當元素數量增加時，可能的組合會快速增加，因此 Backtracking 雖然可以完整找出所有答案，但也需要注意問題的規模。這讓我對之後的 Permutations 和其他 Backtracking 題目有了更好的基礎。