a456 - 子集合
題目描述
題目要求輸出一個集合的所有子集合。集合的元素範圍是從 1 到 N，其中 N 是輸入的整數。輸出需要按照子集合的大小從小到大排序，如果大小相同，則按照子集合中的元素從小到大排序。空集合必須輸出為 {0}。
解題思路
這題可以使用深度優先搜尋 (DFS) 或回溯法來解決。基本思路是遞迴地遍歷所有可能的子集合。在每一層遞迴中，我們決定是否將當前元素包含在子集合中。如果包含，則將其添加到子集合中，並遞迴地處理下一個元素。如果不包含，則跳過當前元素，並遞迴地處理下一個元素。
程式碼中 dfs 函數實現了這個遞迴過程。it 參數表示當前處理的元素索引，l 參數表示子集合的大小。在 dfs 函數中，我們首先檢查是否已經生成了一個完整的子集合（it == l）。如果是，則輸出該子集合。否則，我們遍歷所有可能的元素值，並遞迴地調用 dfs 函數。
為了確保輸出符合題目要求的順序，我們在遍歷元素值時，從上一個元素值加 1 開始。這樣可以避免生成重複的子集合，並確保子集合按照元素大小排序。
複雜度分析
- 時間複雜度: O(2^N)
- 空間複雜度: O(N)