題目連結(https://leetcode.com/problems/subsets/description/)

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

backtracking 題

1. Repeat（題目重複確認）

• 輸入：整數陣列 nums ，陣列中的值都是獨立元素
• 輸出：由這些不同元素構成的子集，也就是 冪集（power set）
• 前提：
  • 1 <= nums.length <= 10
  • 10 <= nums[i] <= 10
  • All the numbers of nums are unique.

2. Examples（舉例確認理解）

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

3. Approach（解題思路）

方法 ：回溯（Backtracking）

• 每次遞迴時移出或加入後的集合都是一種新組合，所以都要保留
• 時間複雜度：O(2ⁿ)
  • n 個元素，每個元素都有選/不選兩種狀態
  • 總共 2ⁿ 種組合
• 空間複雜度：O(n)
  • 遞迴深度最多 n 層，subset 最多儲存 n 個元素

4. Code（C++）

backtracking

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res; // 儲存所有子集合
        vector<int> subset;      // 當前正在建立的子集合

        setcreation(nums, 0, res, subset);
        return res;
    }

    void setcreation(vector<int>& nums, int index, vector<vector<int>>& res, vector<int>& subset){
        // 1️⃣ 終止條件：遍歷完所有元素
        if(index == nums.size()){
            res.push_back(subset);
            return;
        }
		// 2️⃣ 選擇包含當前元素 nums[index]
        subset.push_back(nums[index]); // 做選擇
        setcreation(nums, index+1, res, subset); // 遞迴
		// 3️⃣ 回溯：撤銷選擇
        subset.pop_back(); // 恢復
        // 4️⃣ 選擇不包含當前元素
        setcreation(nums, index+1, res, subset);
    }
};

5. Test 範例

決策樹（二元樹）
                    []
                   /  \
              選1 /     \ 不選1
                /        \
              [1]         []
             /  \        /  \
        選2 /    \不2    /    \ 
          /      \     /      \
       [1,2]    [1]  [2]      []
       /  \     / \  / \     / \
      /    \   /   \/   \   /   \
  [1,2,3][1,2][1,3][1][2,3][2][3][]

6. 相關題目與延伸概念

• **Subsets II Medium**
• **Letter Case Permutation Medium**

7. 補充：語法＆注意事項

1. &引用法

void setcreation(vector<int>& subset)  // ✓ 參考：共用同一個陣列
void setcreation(vector<int> subset)   // ✗ 值：每次複製，沒有回溯效果

2. 回溯法

void backtrack(參數) {
    if (終止條件) {
        收集結果;
        return;
    }
    
    for (每個選擇) {
        做選擇;           // subset.push_back()
        backtrack(下一步);  // 遞迴
        撤銷選擇;         // subset.pop_back()
    }
}

ps. 部分內容經 AI 協助整理