leadcode的Hot100系列--78. 子集

看一個數組的子集有多少，其實就是排列組合，
比如：[0,1] 對應的子集有：[] [0] [1] [1,1] 這四種。
一般對應有兩種方法：位運算 和 回溯。
這裡先使用位運算來做。

位運算

一個長度為n的數組，對其做排列組合，可以理解為：這n個數字中，有哪些是存在的，哪些是不存在的。
例如，數組為[1,2,3]，可以組合為：[1,2]，則說明1和2是存在的，3是不存在的，
我們可以這麼規定一下： 用1標記為存在，0標記為不存在，
那麼[1,2]這個組合就可以用 110來標記，[1,3]的組合就可以用101來標記，[]的組合就可以用000來標記。
（註：這裡為方便理解，將數組直觀的位置與標記一一對應，而不考慮數組下標，
實際代碼中，是用下標來做對應的）
這樣的話：

數組的排列組合問題，就轉換為每個數字的存在或者不存在的問題。

這裡有三個數字，每個數字都會有存在和不存在的兩種情況，總共就會有8種排列，分別是：
000，001， 010， 011， 100， 101， 110， 111
對應的數組分別是：
[]，[3]，[2]， [2,3]， [1]， [1,3]， [1,2]， [1,2,3]

重點來了：如果把上面的01標記看成二進位數字的，那對應的十進位數字就是0,1,2,3,4,5,6,7。
這裡先統稱這些數字為flag（用來標記對應位置的數字是否存在）。
所以，當我已經知道總共的組合有n種的時候，那麼就會有 0 到 (n-1) 個 flag 來標記對應位置的數字是否存在。
那麼代碼中是怎麼對應的呢？這次用數組[6,7,8]來舉例。
數字6，7，8對應的下標分別是 0，1，2，對應的位置就是 (1 << 下標)，
那麼：6對應的是flag中的第1位（1<<0），7對應的是flag中的2位（1<<1），8對應的是flag中的第3位（1<<2）。
所以，實際代碼中 當flag = 1 （二進位位001）的時候，對應的組合是 [6]，flag = 3（二進位位011）的時候，對應的組合是[6,7]。

ps：因為題目要求輸出的形式是：[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]，
這個的話，感覺用c不太好實現，所以就偷偷用了python來實現了，但原理還是一樣的！

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        subList = []
        length = len(nums)
        totalCount = pow(2, length)     # 得到子集的總個數
        for flag in range(totalCount):   # 遍歷各個flag標記
            sub = []
            for xiabiao in range(length):  # 遍曆數組下標，查看對應位置的數字是否存在
                if flag & (1<<xiabiao):
                    sub.append(nums[xiabiao])  # 如果對應的數字存在，就把該數字放入新數組中
            subList.append(sub)
        return subLis

遞歸放在下一篇講解。