swift算法：子集

1、描述

給定一組不含重複元素的整數數組 nums，傳回該數組所有可能的子集（幂集）。

說明：解集不能包含重複的子集

例：輸入：nums = [1, 2, 3]

        輸出：[ [3], [1], [2], [1, 2, 3], [1, 3], [2, 3], [1, 2], [] ]  

2、算法

1）二進制位

思想：集合的每個元素，都有可以選或不選，用二進制和位運算，可以很好的表示

2）枚舉

解法一：逐個枚舉

思想：逐個枚舉，空集的幂集隻有空集，每增加一個元素，讓之前幂集中的每個集合，追加這個元素，就是新增的子集

解法二：遞歸枚舉

3）疊代

解法一

思想：解法一的疊代法，是直接從結果上進行分類，将子數組的長度分為長度是 1 的，2 的 .... n 的。

           想找出數組長度 1 的所有解，然後再在長度為 1 的所有解上加 1 個數字變成長度為 2 的所有解，同樣的直到 n。         

示意圖：

         第一次循環：     [1]           [2]        [3]

         第二次循環：[1, 2] [1, 3]    [2, 3]

         第三次循環：[1, 2, 3]

解法二

思想：我們還可以從條件上入手，先隻考慮給定數組的 1 個元素的所有子數組，然後再考慮數組的 2 個元素的所有子數組 ... 最後再考慮數組的 n 個元素的所有子數組。求 k 個元素的所有子數組，隻需要在 k - 1 個元素的所有子數組裡邊加上 nums [ k ] 即可。

圖示：

                                                                         []      -->  初始化空

                                                                []      [1]     -->   [1]

                                              []    [1]     [2]     [1,2]   -->   [1,2]

          []   [1]   [2]   [1, 2]  [3]  [1,3]   [2,3]   [1,2,3] -->   [1,2,3]

4）回溯

思想：集合中每個元素的選和不選，構成了一個滿二叉狀态樹，比如，左子樹是不選，右子樹是選，從根節點、到葉子節點的所有路徑，構成了所有子集。通過回溯，跳過一些節點