全组合 五种写法

用子集最后一个元素判断数字是否已经用过

# nums.sort()
# dfs1(nums, [], result)
def dfs1(nums, subset, result):
    result.append(subset[:])
    
    for n in nums:
        if not subset or n > subset[-1]:
            subset.append(n)
            dfs1(nums, subset, result)
            subset.pop()
 
# input:  [1,2,3]
# output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

思路同上，用下标判断

# dfs2(nums, 0, [], result)
def dfs2(nums, start, subset, result):
    result.append(subset[:])
        
    for i in range(start, len(nums)):
        # 如果有重复数字，则前面先 nums.sort() 排序，这里即可去重
        #if i > index and nums[i] == nums[i - 1]:
        #    continue
        subset.append(nums[i])
        dfs2(nums, i + 1, subset, result)
        subset.pop()
        
# input:  [1,2,3]
# output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

分治的思想，对于每个元素进行选择、不选择两种操作，递归结束条件是所有元素都操作过

# dfs3(nums, 0, [], result)
def dfs3(nums, index, subset, result):
    if index == len(nums):
        result.append(subset[:])
        return
    
    # 选择，入集合，递归操作下一个元素，完成后回溯
    subset.append(nums[index])
    dfs3(nums, index + 1, subset, result)
    subset.pop()
    # 不选择，直接递归操作下一个元素
    dfs3(nums, index + 1, subset, result)
    
# input:  [1,2,3]
# output: [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

BFS，每层都是结果之一，下一层追加一个没有选过的数字

# bfs(nums, result)
def bfs(nums, result):
    from collections import deque
    q = deque()
    q.append([])
    while q:
        for _ in range(len(q)):
            subset = q.popleft()
            result.append(subset[:])
            for n in nums:
                if not subset or n > subset[-1]:
                    q.append(subset + [n])

基于位运算的做法，感觉通用性不大

def bitseach(nums, result):
    size = len(nums)
    
    for i in range(1<<size):
        subset = []
        for j in range(size):
            if i & (1 << j) != 0:
                subset.append(nums[j])
        result.append(subset[:])