DFS/Backtracking Algorithm

Overview

The template for backtracking is as follows:

result = []
def backtrack(path, choice_list):
    if end_condition_met:
        result.add(path)
        return

    for choice in choice_list:
        # make a choice
        backtrack(path, choice_list)
        # !!! undo

Permutations (Leetcode 46)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        self.results = []
        tracks = []
        used = [False] * len(nums)
        self.backtrack(nums, tracks, used)

        return self.results



    def backtrack(self, nums, tracks, used):

        if len(tracks) == len(nums):
            self.results.append(tracks.copy())
            return 

        for i in range(len(nums)):
            if used[i]:
                continue

            tracks.append(nums[i])
            used[i] = True
            self.backtrack(nums, tracks, used)

            tracks.pop()
            used[i] = False

Sudoku and N-Queens

Sudoku Solver (Leetcode 37)

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        n_rows, n_cols = 9, 9

        def isValid(r, c, num):
            for i in range(9):
                if board[i][c] == num or board[r][i] == num:
                    return False

            start_row, start_col = (r // 3) * 3, (c // 3) * 3
            for i in range(3):
                for j in range(3):
                    if board[start_row + i][start_col + j] == num:
                        return False
            return True

        def backtrack(index):
            if index == 81:
                return True

            r, c = index // 9, index % 9
            if board[r][c] != '.':
                return backtrack(index + 1)

            for ch in '123456789':
                if isValid(r, c, ch):
                    board[r][c] = ch

                    if backtrack(index + 1):
                        return True

                    board[r][c] = '.'

            return False

        backtrack(0)

N-Queens (Leetcode 51)

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:

        self.res = []
        board = ['.' * n for _ in range(n)]


        def isValid(board, row, col):
            n = len(board)

            for i in range(row):
                if board[i][col] == 'Q':
                    return False

            for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
                if board[i][j] == 'Q':
                    return False

            for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
                if board[i][j] == 'Q':
                    return False
            return True

        def backtrack(board, row):
            if row == n:
                self.res.append(board[:])
                return

            for col in range(n):
                if not isValid(board, row, col):
                    continue

                board[row] = board[row][:col] + 'Q' + board[row][col+1:]
                backtrack(board, row+1)
                board[row] = board[row][:col] + '.' + board[row][col+1:]

        backtrack(board, 0)
        return self.res

N-Queens II (Leetcode 52)

class Solution:
    def totalNQueens(self, n: int) -> int:

        self.res = 0
        board = ['.' * n for _ in range(n)]


        def isValid(board, row, col):
            n = len(board)

            for i in range(row):
                if board[i][col] == 'Q':
                    return False

            for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
                if board[i][j] == 'Q':
                    return False

            for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
                if board[i][j] == 'Q':
                    return False
            return True

        def backtrack(board, row):
            if row == n:
                self.res += 1
                return

            for col in range(n):
                if not isValid(board, row, col):
                    continue

                board[row] = board[row][:col] + 'Q' + board[row][col+1:]
                backtrack(board, row+1)
                board[row] = board[row][:col] + '.' + board[row][col+1:]

        backtrack(board, 0)
        return self.res

Permutations & Combinations & Subsets

Subsets (Leetcode 78)

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:

        self.res = []
        tracks = []
        start = 0

        self.backtrack(nums, tracks, start)

        return self.res

    def backtrack(self, nums, tracks, start):

        self.res.append(tracks.copy())

        for i in range(start, len(nums)):
            tracks.append(nums[i])
            self.backtrack(nums, tracks, i+1)
            tracks.pop()

Combinations (Leetcode 77)

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.res = []
        tracks = []
        start = 0

        nums = range(1, n+1)

        self.backtrack(nums, tracks, start, k)

        return self.res

    def backtrack(self, nums, tracks, start, k):

        if len(tracks) == k:
            self.res.append(tracks.copy())
            return

        for i in range(start, len(nums)):
            tracks.append(nums[i])
            self.backtrack(nums, tracks, i+1, k)
            tracks.pop()

Subsets II (Leetcode 90)

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

        self.res = []
        tracks = []
        start = 0

        nums.sort()

        self.backtrack(nums, tracks, start)

        return self.res

    def backtrack(self, nums, tracks, start):

        self.res.append(tracks.copy())

        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue

            tracks.append(nums[i])
            self.backtrack(nums, tracks, i+1)
            tracks.pop()

Combination Sum II (Leetcode 40)

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        tracks = []

        candidates.sort()

        self.backtrack(candidates, tracks, target, 0)

        return self.res


    def backtrack(self, candidates, tracks, target, start):
        if target == 0:
            self.res.append(tracks.copy())
            return

        for i in range(start, len(candidates)):
            if candidates[i] > target:
                continue

            if i > start and candidates[i] == candidates[i-1]:
                continue

            tracks.append(candidates[i])

            self.backtrack(candidates, tracks, target - candidates[i], i+1)
            tracks.pop()

Permutations II (Leetcode 47)

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:

        self.res = []
        tracks = []
        used = [False] * len(nums)
        nums.sort()

        self.backtrack(nums, tracks, used)

        return self.res


    def backtrack(self, nums, tracks, used):

        if len(nums) == len(tracks):
            self.res.append(tracks.copy())

        for i in range(len(nums)):
            if i>0 and nums[i-1] == nums[i] and (not used[i-1]):
                continue
            if used[i]:
                continue
            tracks.append(nums[i])
            used[i] = True

            self.backtrack(nums, tracks, used)
            tracks.pop()
            used[i] = False

Combination Sum (Leetcode 39)

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        self.res = []
        tracks = []
        self.backtrack(candidates, tracks, target, 0)

        return self.res


    def backtrack(self, candidates, tracks, target, start):

        if target == 0:
            self.res.append(tracks.copy())

        for i in range(start, len(candidates)):
            if candidates[i] > target:
                continue

            tracks.append(candidates[i])
            self.backtrack(candidates, tracks, target - candidates[i], i)
            tracks.pop()

Island

Overview

The 2D array can always be considered as a 4-ary tree, with 4 neighbors as children. The template is as follows:

def dfs(grid: List[List[int]], i: int, j: int, visited: List[List[bool]]) -> None:
    m, n = len(grid), len(grid[0])
    if i < 0 or j < 0 or i >= m or j >= n:
        return

    if visited[i][j]:
        return

    visited[i][j] = True

    dfs(grid, i - 1, j, visited) # up
    dfs(grid, i + 1, j, visited) # down
    dfs(grid, i, j - 1, visited) # left
    dfs(grid, i, j + 1, visited) # right

Number of Islands (Leetcode 200)

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:

        def dfs(grid, row, col):
            if row <0 or row >= len(grid) or col <0 or col >= len(grid[0]):
                return 
            if grid[row][col] == '0':
                return
            grid[row][col] = '0'

            dfs(grid, row, col+1)
            dfs(grid, row, col-1)
            dfs(grid, row+1, col)
            dfs(grid, row-1, col)

        res = 0
        n_row, n_col = len(grid), len(grid[0])

        for row in range(n_row):
            for col in range(n_col):
                if grid[row][col] == '1':
                    res += 1

                    dfs(grid, row, col)

        return res

Number of Closed Islands (Leetcode 1254)

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:

        def dfs(grid, row, col):
            if row <0 or row >= len(grid) or col <0 or col >= len(grid[0]):
                return 
            if grid[row][col] == 1:
                return
            grid[row][col] = 1

            dfs(grid, row, col+1)
            dfs(grid, row, col-1)
            dfs(grid, row+1, col)
            dfs(grid, row-1, col)

        res = 0
        n_row, n_col = len(grid), len(grid[0])

        for row in range(n_row):
            dfs(grid, row, 0)
            dfs(grid, row, n_col-1)

        for col in range(n_col):
            dfs(grid, 0, col)
            dfs(grid, n_row-1, col)

        for row in range(n_row):
            for col in range(n_col):
                if grid[row][col] == 0:
                    res += 1

                    dfs(grid, row, col)

        return res

Max Area of Island (Leetcode 695)

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

        def dfs(grid, row, col):
            if row <0 or row >= len(grid) or col <0 or col >= len(grid[0]):
                return 0
            if grid[row][col] == 0:
                return 0
            grid[row][col] = 0

            count = dfs(grid, row, col+1)
            count += dfs(grid, row, col-1)
            count += dfs(grid, row+1, col)
            count += dfs(grid, row-1, col)

            return count + 1

        max_count = 0
        n_row, n_col = len(grid), len(grid[0])

        for row in range(n_row):
            for col in range(n_col):
                if grid[row][col] == 1:
                    count = dfs(grid, row, col)
                    if count > max_count:
                        max_count = count

        return max_count

Count Sub Islands (Leetcode 1905)

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:


        def dfs(grid, row, col):
            if row <0 or row >= len(grid) or col <0 or col >= len(grid[0]):
                return 
            if grid[row][col] == 0:
                return
            grid[row][col] = 0

            dfs(grid, row, col+1)
            dfs(grid, row, col-1)
            dfs(grid, row+1, col)
            dfs(grid, row-1, col)

        res = 0
        n_row, n_col = len(grid1), len(grid1[0])

        for row in range(n_row):
            for col in range(n_col):
                if grid1[row][col] == 0 and grid2[row][col] == 1:
                    dfs(grid2, row, col)


        for row in range(n_row):
            for col in range(n_col):
                if grid2[row][col] == 1:
                    res += 1
                    dfs(grid2, row, col)






        return res

Number of Distinct Islands (Leetcode 694)