Subsets

Posted on

使用 BFS 解决一系列排列、组合问题。基本上对 queue 进行迭代就可以了（需要 popleft 时选择 deque），但有时需要用到递归。

A huge number of coding interview problems involve dealing with Permutations and Combinations of a given set of elements. This pattern describes an efficient breadth-first search approach to handle all these problems.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
"""Iteration"""
queue = deque([[]])
for num in sorted(nums):  # handle duplicates
    for _ in range(len(queue)):
        item = queue.popleft()
        cand = item + [num]
        if cand not in queue:
            queue.append(cand)
        
        queue.append(item)

return queue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""Recursion"""
@cache
def build(start, end):
    if start > end:
        return [None]

    trees = []
    for val in range(start, end + 1):
        # divide & conquer
        l = build(start, val - 1)
        r = build(val + 1, end)

        for x in l:
            for y in r:
                root = TreeNode(val)
                root.left = x
                root.right = y
                trees.append(root)

    return trees

return build(1, n)

LeetCode

78. Subsets
90. Subsets II
46. Permutations
784. Letter Case Permutation
22. Generate Parentheses
320. Generalized Abbreviation
241. Different Ways to Add Parentheses
95. Unique Binary Search Trees II
96. Unique Binary Search Trees