## Data Structure and Algorithm 6 | P-NP and Backtracking

#### 1. P-NP Problem

(1) Longest Increasing Subsequence

Leetcode: 300.

Pseudocode: DP, Time complexity $O(n^2)$.

1L[i] = 1 + max{ L[j]: for all nums[j] < nums[i] and j < i }

Python code,

​x1L = [1] * len(nums)2​3for i in range(len(nums)):4    for j in range(i):5        if nums[i] > nums[j]:6            L[i] = max(L[i], L[j] + 1)7​8return max(L)

(2) Polynomal Time

An algorithm runs in polynomial time if its runtime is some polynomial in $n$, which can be written as $O(n^k)$.

(3) Cobham-Edmonds Thesis

A language $L$ can be decided efficiently if and only if it can be decided in time $O(n^k)$ for some $k \in \mathbb{N}$.

For example,

can be decided efficiently but,

can not be decided efficiently.

(4) Complexity Class P

The complexity class $P$ is a class that contains all the problems that can be solved in polynomial time,

Where $TM$ stands for Turing Machine.

Common P problems are,

• graph connectivity
• primality testing
• maximum matching
• remoteness testing
• linear programming
• string transform distance
• Etc.

(5) Non-deterministic Turing machine

A nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. For example, BST is an NTM because its time complexity is the height of the tree.

(6) NTM to TM Theorem

For any NTM with time complexity $f(n)$, there is a TM with time complexity $2^{O(f(n))}$.

(7) Complexity Class NP

The complexity class NP (nondeterministic polynomial time) contains all problems that can be solved in polynomial time by an NTM.

Common NP problems are,

• Solve sudoku
• Knapsack probelm
• Travelling salesman
• Graph coloring

From the definition, we can easily know that,

But it is still the most important question in theorical computer science that if

It can be explained simply as if a solution to a problem can be checked efficiently, can that problem be solved efficiently?

#### 2. Backtracking

(1) Definition

Backtracking is a general algorithm for finding the solutions to some computational problems. It abandons a candidate (called backtrack) as soon as it determinates the candidate can not possibily be completed to a valid solution. Backtracking is commonly used to solve some NP-complete questions.

(2) Template

xxxxxxxxxx131def backtrack(case):2​3    if find_solution(case):4        return5        6    for next_case in cases:7      8        if not is_valid(next_case):9            continue10        11        set_next()12        backtrack(next_case)13        reset_last()

(3) Crosswords I

Find a specific word in a matrix.

Leetcode 79.

xxxxxxxxxx331class Solution:2    def exist(self, board: List[List[str]], word: str) -> bool:3        self.m = len(board)4        self.n = len(board[0])5        self.board = board6        7        for i in range(self.m):8            for j in range(self.n):9                if self.backtrack(i, j, word):10                    return True11​12        return False13    14    def backtrack(self, row, col, suffix):15        16        if len(suffix) == 0:17            return True18        19        if row < 0 or row == self.m or col < 0 or col == self.n:20            return False21        22        if self.board[row][col] != suffix[0]:23            return False24        25        self.board[row][col] = '#'26        27        for roffset, coffset in [(0,1), (1,0), (0,-1), (-1,0)]:28            if self.backtrack(row+roffset, col+coffset, suffix[1:]):29                self.board[row][col] = suffix[0]30                return True31            32        self.board[row][col] = suffix[0]33        return False

(4) Crosswords II

Clean a room by robot.

Leetcode 489.

xxxxxxxxxx301def cleanRoom(self, robot):2    """3    :type robot: Robot4    :rtype: None5    """6    def go_back():7        robot.turnRight()8        robot.turnRight()9        robot.move()10        robot.turnRight()11        robot.turnRight()12​13    def backtrack(cell=(0, 0), direction=0):14        visited.add(cell)15        robot.clean()16​17        for i in range(4):18            new_direction_index = (direction + i) % 419            next_direction = directions[new_direction_index]20            next_cell = (cell[0] + next_direction[0], cell[1] + next_direction[1])21​22            if not next_cell in visited and robot.move():23                backtrack(next_cell, new_direction_index)24                go_back()25​26            robot.turnRight()27​28    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]29    visited = set()30    backtrack()

(5) N-Queens I

Leetcode 51.

Trick 1: how to get the diagonal/anti-diagonal index for a cell in an $n \times n$ matrix.

For an $n \times n$ matrix, there will be $2n - 1$ diagonals or anti-diagonals. So the index of a diagonal can be calculated by,

xxxxxxxxxx11diagonal_in = row_in - col_in

And the index of an anti-diagonal can be calculated by,

xxxxxxxxxx11antidiagonal_in = row_in + col_in

Trick 2: Before we put a queen, we have to check three sets.

• if its column has another queen?
• if its diagonal has another queen?
• if its anti-diagonal has another queen?

We don't need to check the rows because we will only put one queen in each row.

xxxxxxxxxx381class Solution:2    def solveNQueens(self, n: int) -> List[List[str]]:3        4        def backtrack(row, diagonals, antidiagonals, cols, state):5            6            if row == n:7                ans.append(["".join(row) for row in state])8                return9​10            for col in range(n):11                diagonal = row - col12                antidiagonal = row + col13                14                if col in cols:15                    continue16                    17                if diagonal in diagonals:18                    continue19                    20                if antidiagonal in antidiagonals:21                    continue22                    23                state[row][col] = "Q"24                cols.add(col)25                diagonals.add(diagonal)26                antidiagonals.add(antidiagonal)27                28                backtrack(row+1, diagonals, antidiagonals, cols, state)29                30                state[row][col] = "."31                cols.remove(col)32                diagonals.remove(diagonal)33                antidiagonals.remove(antidiagonal)34                35        ans = []36        empty_board = [["."] * n for _ in range(n)]37        backtrack(0, set(), set(), set(), empty_board)38        return ans

(6) N-Queens II

This is just a similar question without requirement for printing the board.

Leetcode 52.

xxxxxxxxxx351class Solution:2    def totalNQueens(self, n: int) -> int:3        4        self.ans = 05        6        def backtrack(row, diagonals, antidiagonals, cols):7            8            if row == n:9                self.ans += 110                return11                12            for col in range(n):13                14                diagonal = row - col15                antidiagonal = row + col16                17                if col in cols:18                    continue19                if diagonal in diagonals:20                    continue21                if antidiagonal in antidiagonals:22                    continue23                    24                cols.add(col)25                diagonals.add(diagonal)26                antidiagonals.add(antidiagonal)27                28                backtrack(row+1, diagonals, antidiagonals, cols)29                30                cols.remove(col)31                diagonals.remove(diagonal)32                antidiagonals.remove(antidiagonal)33            34        backtrack(0, set(), set(), set())35        return self.ans

(6) Valid Sudoku

Before we see how to solve a Sudoku, let's first see how we can validate one. This is not a backtracking problem.

Leetcode 36.

xxxxxxxxxx391class Solution:2    def isValidSudoku(self, board: List[List[str]]) -> bool:3        4        m = len(board)5        n = len(board[0])6        7        self.board = board8        self.rows = [set() for _ in range(m)]9        self.cols = [set() for _ in range(m)]10        self.boxs = [set() for _ in range(m)]11        12        for row in range(m):13            for col in range(n):14                if board[row][col] == ".":15                    continue16                17                if not self.isValidCell(row, col):18                    return False19        20        return True21        22    def isValidCell(self, row, col):23        24        val = self.board[row][col]25        box = (row // 3) * 3 + col // 326        27        if val in self.rows[row]:28            return False29        30        if val in self.cols[col]:31            return False32        33        if val in self.boxs[box]:34            return False35        36        self.rows[row].add(val)37        self.cols[col].add(val)38        self.boxs[box].add(val)39        return True

(7) Solve Sudoku

Next, let's solve a Sudoku.

Leetcode: 37.

xxxxxxxxxx791class Solution:2    def solveSudoku(self, board: List[List[str]]) -> None:3        """4        Do not return anything, modify board in-place instead.5        """6        7        self.sudoku_solved = False8        9        def place_number(d, row, col):10            11            if d not in rows[row]:12                rows[row][d] = 113            else:14                rows[row][d] += 115                16            if d not in cols[col]:17                cols[col][d] = 118            else:19                cols[col][d] += 120                21            if d not in boxs[box_index(row, col)]:22                boxs[box_index(row, col)][d] = 123            else:24                boxs[box_index(row, col)][d] += 125                26            board[row][col] = str(d)27            28        def place_next_numbers(row, col):29            if col == N - 1 and row == N - 1:30                self.sudoku_solved = True  31            else:32                if col == N - 1:33                    backtrack(row + 1, 0)34                else:35                    backtrack(row, col + 1)36                37                38        def backtrack(row = 0, col = 0):39            40            if board[row][col] == '.':41                42                for d in range(1, 10):43                    44                    if d in rows[row]:45                        continue46                        47                    if d in cols[col]:48                        continue49                        50                    if d in boxs[box_index(row, col)]:51                        continue52                    53                    place_number(d, row, col)54                    place_next_numbers(row, col)55                    56                    if not self.sudoku_solved:57                        board[row][col] = '.'58                        del rows[row][d]59                        del cols[col][d]60                        del boxs[box_index(row, col)][d]61                        62            else:63                place_next_numbers(row, col)64                    65        n = 366        N = n * n67        box_index = lambda row, col: (row // n ) * n + col // n68        69        rows = [dict() for _ in range(N)]70        cols = [dict() for _ in range(N)]71        boxs = [dict() for _ in range(N)]72        73        for i in range(N):74            for j in range(N):75                if board[i][j] != '.': 76                    d = int(board[i][j])77                    place_number(d, i, j)78        79        backtrack()

(8) Combination

Combination and permutation problems can also be solved by backtracking.

Leetcode 77.

xxxxxxxxxx171class Solution:2    def combine(self, n: int, k: int) -> List[List[int]]:3        self.ans = []4        self.n = n5        self.k = k6        self.backtrack()7        return self.ans8    9    def backtrack(self, first=1, curr=[]):10        11        if len(curr) == self.k:12            self.ans.append(curr.copy())13            14        for i in range(first, self.n + 1):15            curr.append(i)16            self.backtrack(i+1, curr)17            curr.pop()

(9) Combination Sum I

Find all the combinations that sums up to a target value.

Leetcode 39.

xxxxxxxxxx231class Solution:2    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:3        result = []4        self.ans = []5        self.candidates = candidates6        self.target = target7        self.backtrack()8        9        return self.ans10        11    def backtrack(self, index=0, curr=[]):12        13        if sum(curr) == self.target:14            self.ans.append(curr.copy())15        16        if sum(curr) > self.target:17            return18            19        for i in range(index, len(self.candidates)):20            21            curr.append(self.candidates[i])22            self.backtrack(i, curr)23            curr.pop()

(10) Subset

Get the list of all the subsets of a set. Note backtrack doesn't help with this problem because it has to traverse all the cases.

Leetcode 78.

xxxxxxxxxx191class Solution:2    def subsets(self, nums: List[int]) -> List[List[int]]:3        self.ans = []4        self.nums = nums5        for k in range(len(nums) + 1):6            self.backtrack(k)7        return self.ans8        9    def backtrack(self, k, first=0, curr=[]):10        11        if len(curr) == k:12            self.ans.append(curr.copy())13            return14        15        for i in range(first, len(self.nums)):16            17            curr.append(self.nums[i])18            self.backtrack(k, i + 1, curr)19            curr.pop()

(11) Subset II

Everything is similar but this time the set contains duplicated values. So in this question, the backtracking will work for us.

Leetcode 90.

xxxxxxxxxx221class Solution:2    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:3        self.ans = []4        self.nums = sorted(nums)5        for k in range(len(nums) + 1):6            self.backtrack(k)7        return self.ans8        9    def backtrack(self, k, first=0, curr=[]):10        11        if len(curr) == k:12            self.ans.append(curr.copy())13            return14        15        for i in range(first, len(self.nums)):16            17            if i > first and self.nums[i] == self.nums[i-1]:18                continue19            20            curr.append(self.nums[i])21            self.backtrack(k, i + 1, curr)22            curr.pop()

(12) Permutations

Give all the permutations of a list.

Leetcode 46.

xxxxxxxxxx161class Solution:2    def permute(self, nums: List[int]) -> List[List[int]]:3        self.ans = []4        self.nums = nums5        self.backtrack(nums)6        return self.ans7    8    def backtrack(self, nums, curr=[]):9        10        if len(curr) == len(self.nums):11            self.ans.append(curr.copy())12            13        for i in range(len(nums)):14            curr.append(nums[i])15            self.backtrack(nums[:i] + nums[i+1:], curr)16            curr.pop()

(12) Permutations II

Give all the permutations of a list with duplicate values.

Leetcode 47.

xxxxxxxxxx201class Solution:2    def permuteUnique(self, nums: List[int]) -> List[List[int]]:3        self.ans = []4        self.nums = sorted(nums)5        self.backtrack(self.nums)6        return self.ans7    8    def backtrack(self, nums, curr=[]):9        10        if len(curr) == len(self.nums):11            self.ans.append(curr.copy())12            13        for i in range(len(nums)):14            15            if i > 0 and nums[i] == nums[i-1]:16                continue17            18            curr.append(nums[i])19            self.backtrack(nums[:i] + nums[i+1:], curr)20            curr.pop()

(13) Letter Combinations

Leetcode 17.

xxxxxxxxxx331class Solution:2    def letterCombinations(self, digits: str) -> List[str]:3        4        if not digits:5            return []6        7        self.hashmap = {8            '2' : ['a', 'b', 'c'],9            '3' : ['d', 'e', 'f'],10            '4' : ['g', 'h', 'i'],11            '5' : ['j', 'k', 'l'],12            '6' : ['m', 'n', 'o'],13            '7' : ['p', 'q', 'r', 's'],14            '8' : ['t', 'u', 'v'],15            '9' : ['w', 'x', 'y', 'z']16        }17        self.ans = []18        self.backtrack(digits, [])19        return self.ans20    21    def backtrack(self, nums, curr):22        23        if not nums:24            self.ans.append("".join(curr))25            return 26        27        letter_list = self.hashmap[nums[0]]28        29        for letter in letter_list:30            curr.append(letter)31            self.backtrack(nums[1:], curr)32            curr.pop()33