Backtracking Permutation

Table of Contents

• 46. Permutations (Medium)
• 3376. Minimum Time to Break Locks I (Medium)
• 51. N-Queens (Hard)
• 52. N-Queens II (Hard)
• 2850. Minimum Moves to Spread Stones Over Grid (Medium)
• 1718. Construct the Lexicographically Largest Valid Sequence (Medium)
• 1307. Verbal Arithmetic Puzzle (Hard)
• 2014. Longest Subsequence Repeated k Times (Hard)
• 267. Palindrome Permutation II (Medium) 👑

46. Permutations

• LeetCode | LeetCode CH (Medium)

• Tags: array, backtracking

46. Permutations - Python Solution

from typing import List


# Backtracking
def permute(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    path, res = [], []
    used = [False for _ in range(n)]

    def dfs(x: int):
        if x == n:
            res.append(path[:])
            return

        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            dfs(x + 1)
            path.pop()
            used[i] = False

    dfs(0)

    return res


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

3376. Minimum Time to Break Locks I

• LeetCode | LeetCode CH (Medium)

• Tags: array, dynamic programming, backtracking, bit manipulation, depth first search, bitmask

51. N-Queens

• LeetCode | LeetCode CH (Hard)

• Tags: array, backtracking

• Hard
• N-Queens
• N 皇后

51. N-Queens - Python Solution

from typing import List


# Backtracking
def solveNQueens(n: int) -> List[List[str]]:
    res = []
    board = ["." * n for _ in range(n)]

    def dfs(row):
        if row == n:
            res.append(board[:])
            return None
        for col in range(n):
            if is_valid(row, col, board):
                board[row] = board[row][:col] + "Q" + board[row][col + 1 :]
                dfs(row + 1)
                board[row] = board[row][:col] + "." + board[row][col + 1 :]

    def is_valid(row, col, chessboard):
        for i in range(row):
            if chessboard[i][col] == "Q":
                return False

        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if chessboard[i][j] == "Q":
                return False
            i -= 1
            j -= 1

        i, j = row - 1, col + 1
        while i >= 0 and j < len(chessboard):
            if chessboard[i][j] == "Q":
                return False
            i -= 1
            j += 1

        return True

    dfs(0)

    return [["".join(row) for row in i] for i in res]


# Backtracking
def solveNQueens2(n: int) -> List[List[str]]:
    res = []
    queens = [0] * n
    col = [False] * n
    diag1 = [False] * (n * 2 - 1)
    diag2 = [False] * (n * 2 - 1)

    def dfs(r: int) -> None:
        if r == n:
            res.append(["." * c + "Q" + "." * (n - 1 - c) for c in queens])
            return

        for c, ok in enumerate(col):
            if not ok and not diag1[r + c] and not diag2[r - c]:
                queens[r] = c
                col[c] = diag1[r + c] = diag2[r - c] = True
                dfs(r + 1)
                col[c] = diag1[r + c] = diag2[r - c] = False

    dfs(0)

    return res


if __name__ == "__main__":
    print(solveNQueens(4))
    # [['.Q..', '...Q', 'Q...', '..Q.'],
    #  ['..Q.', 'Q...', '...Q', '.Q..']]
    print(solveNQueens(1))
    # [['Q']]
    print(solveNQueens2(4))
    # [['.Q..', '...Q', 'Q...', '..Q.'],
    #  ['..Q.', 'Q...', '...Q', '.Q..']]
    print(solveNQueens2(1))
    # [['Q']]

52. N-Queens II

• LeetCode | LeetCode CH (Hard)

• Tags: backtracking

2850. Minimum Moves to Spread Stones Over Grid

• LeetCode | LeetCode CH (Medium)

• Tags: array, dynamic programming, breadth first search, matrix

1718. Construct the Lexicographically Largest Valid Sequence

• LeetCode | LeetCode CH (Medium)

• Tags: array, backtracking

1307. Verbal Arithmetic Puzzle

• LeetCode | LeetCode CH (Hard)

• Tags: array, math, string, backtracking

2014. Longest Subsequence Repeated k Times

• LeetCode | LeetCode CH (Hard)

• Tags: string, backtracking, greedy, counting, enumeration

267. Palindrome Permutation II

• LeetCode | LeetCode CH (Medium)

• Tags: hash table, string, backtracking

Comments