# ===== CodeLab: algo-backtrack =====
# 以下代码片段按文章出现顺序拼接, 共 6 段

# ----- 片段 1 (python) -----
def backtrack(path, choices):
    if 满足结束条件:
        results.append(path[:])   # 记录结果,注意深拷贝
        return
    for c in choices:
        path.append(c)            # 做选择
        backtrack(path, 更新后的choices)
        path.pop()                # 撤销选择,回到岔路口

# ----- 片段 2 (python) -----
def permute(nums):
    res = []
    n = len(nums)

    def dfs(path, used):
        if len(path) == n:          # 结束条件:选满 n 个
            res.append(path[:])     # 深拷贝!直接 append(path) 会出错
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            dfs(path, used)
            path.pop()              # 撤销
            used[i] = False         # 撤销标记

    dfs([], [False] * n)
    return res

for p in permute([1, 2, 3]):
    print(p)
# [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

# ----- 片段 3 (python) -----
def subsets(nums):
    res = []

    def dfs(start, path):
        res.append(path[:])         # 当前路径就是一个子集
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1, path)        # 只能选 i 后面的数
            path.pop()

    dfs(0, [])
    return res

print(subsets([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

# ----- 片段 4 (python) -----
def combine(n, k):
    res = []

    def dfs(start, path):
        if len(path) == k:
            res.append(path[:])
            return
        # 剪枝:就算把 i..n 全选上也凑不满 k 个,就停
        for i in range(start, n + 1):
            if len(path) + (n - i + 1) < k:
                break
            path.append(i)
            dfs(i + 1, path)
            path.pop()

    dfs(1, [])
    return res

print(combine(4, 2))
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

# ----- 片段 5 (python) -----
def solve_n_queens(n):
    res = []
    board = [['.'] * n for _ in range(n)]
    cols = set()
    diag1 = set()   # row - col:主对角线
    diag2 = set()   # row + col:副对角线

    def dfs(row):
        if row == n:
            res.append([''.join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue          # 被攻击,跳过
            board[row][col] = 'Q'
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            dfs(row + 1)
            board[row][col] = '.'   # 撤销
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    dfs(0)
    return res

for b in solve_n_queens(4):
    print('\n'.join(b))
    print()
# .Q..  ...Q  Q...  ..Q.
# ...Q  Q...  ..Q.  .Q..
# Q...  ..Q.  ...Q  ..Q.
# ..Q.  .Q..  .Q..  Q...

# ----- 片段 6 (python) -----
def subsets_with_dup(nums):
    nums.sort()          # 排序是去重的前提
    res = []

    def dfs(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue          # 同一层去重
            path.append(nums[i])
            dfs(i + 1, path)
            path.pop()

    dfs(0, [])
    return res

print(subsets_with_dup([1, 2, 2]))
# [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]