Data_Structure_and_Algorithm

Data Structure and Algorithm 6 | P-NP and Backtracking

0_QXrDY4nVmhZ1umbX

1. P-NP Problem

(1) Longest Increasing Subsequence

Leetcode: 300.

$O(n^2)$ .


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

Python code,


x
1
L = [1] * len(nums)
2
3
for 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
8
return max(L)

(2) Polynomal Time

$n$ $O(n^k)$ .

(3) Cobham-Edmonds Thesis

$L$ $O(n^k)$ $k \in \mathbb{N}$ .

For example,

n^{100000000000000}

can be decided efficiently but,

1.0000000000001^n

can not be decided efficiently.

(4) Complexity Class P

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

P = \{L\ |\text{ There is a polynomial-time decider (TM) for } L\}

$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

$f(n)$ $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.

NP = \{L\ |\text{ There is a NTM that decides }\ L \text{ in non-deterministic polynomial time.}\}

Common NP problems are,

Solve sudoku
Knapsack probelm
Travelling salesman
Graph coloring

From the definition, we can easily know that,

P \subseteq NP

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

P = NP

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


xxxxxxxxxx
13
1
def backtrack(case):
2
3
    if find_solution(case):
4
        return
5
        
6
    for next_case in cases:
7
      
8
        if not is_valid(next_case):
9
            continue
10
        
11
        set_next()
12
        backtrack(next_case)
13
        reset_last()

(3) Crosswords I

Find a specific word in a matrix.

Leetcode 79.


xxxxxxxxxx
33
1
class 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 = board
6
        
7
        for i in range(self.m):
8
            for j in range(self.n):
9
                if self.backtrack(i, j, word):
10
                    return True
11
12
        return False
13
    
14
    def backtrack(self, row, col, suffix):
15
        
16
        if len(suffix) == 0:
17
            return True
18
        
19
        if row < 0 or row == self.m or col < 0 or col == self.n:
20
            return False
21
        
22
        if self.board[row][col] != suffix[0]:
23
            return False
24
        
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 True
31
            
32
        self.board[row][col] = suffix[0]
33
        return False

(4) Crosswords II

Clean a room by robot.

Leetcode 489.


xxxxxxxxxx
30
1
def cleanRoom(self, robot):
2
    """
3
    :type robot: Robot
4
    :rtype: None
5
    """
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) % 4
19
            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 $n \times n$ matrix.

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


xxxxxxxxxx
1
1
diagonal_in = row_in - col_in

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


xxxxxxxxxx
1
1
antidiagonal_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.


xxxxxxxxxx
38
1
class 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
                return
9
10
            for col in range(n):
11
                diagonal = row - col
12
                antidiagonal = row + col
13
                
14
                if col in cols:
15
                    continue
16
                    
17
                if diagonal in diagonals:
18
                    continue
19
                    
20
                if antidiagonal in antidiagonals:
21
                    continue
22
                    
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.


xxxxxxxxxx
35
1
class Solution:
2
    def totalNQueens(self, n: int) -> int:
3
        
4
        self.ans = 0
5
        
6
        def backtrack(row, diagonals, antidiagonals, cols):
7
            
8
            if row == n:
9
                self.ans += 1
10
                return
11
                
12
            for col in range(n):
13
                
14
                diagonal = row - col
15
                antidiagonal = row + col
16
                
17
                if col in cols:
18
                    continue
19
                if diagonal in diagonals:
20
                    continue
21
                if antidiagonal in antidiagonals:
22
                    continue
23
                    
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.


xxxxxxxxxx
39
1
class Solution:
2
    def isValidSudoku(self, board: List[List[str]]) -> bool:
3
        
4
        m = len(board)
5
        n = len(board[0])
6
        
7
        self.board = board
8
        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
                    continue
16
                
17
                if not self.isValidCell(row, col):
18
                    return False
19
        
20
        return True
21
        
22
    def isValidCell(self, row, col):
23
        
24
        val = self.board[row][col]
25
        box = (row // 3) * 3 + col // 3
26
        
27
        if val in self.rows[row]:
28
            return False
29
        
30
        if val in self.cols[col]:
31
            return False
32
        
33
        if val in self.boxs[box]:
34
            return False
35
        
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.


xxxxxxxxxx
79
1
class 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 = False
8
        
9
        def place_number(d, row, col):
10
            
11
            if d not in rows[row]:
12
                rows[row][d] = 1
13
            else:
14
                rows[row][d] += 1
15
                
16
            if d not in cols[col]:
17
                cols[col][d] = 1
18
            else:
19
                cols[col][d] += 1
20
                
21
            if d not in boxs[box_index(row, col)]:
22
                boxs[box_index(row, col)][d] = 1
23
            else:
24
                boxs[box_index(row, col)][d] += 1
25
                
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
                        continue
46
                        
47
                    if d in cols[col]:
48
                        continue
49
                        
50
                    if d in boxs[box_index(row, col)]:
51
                        continue
52
                    
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 = 3
66
        N = n * n
67
        box_index = lambda row, col: (row // n ) * n + col // n
68
        
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.


xxxxxxxxxx
17
1
class Solution:
2
    def combine(self, n: int, k: int) -> List[List[int]]:
3
        self.ans = []
4
        self.n = n
5
        self.k = k
6
        self.backtrack()
7
        return self.ans
8
    
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.


xxxxxxxxxx
23
1
class Solution:
2
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
3
        result = []
4
        self.ans = []
5
        self.candidates = candidates
6
        self.target = target
7
        self.backtrack()
8
        
9
        return self.ans
10
        
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
            return
18
            
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.


xxxxxxxxxx
19
1
class Solution:
2
    def subsets(self, nums: List[int]) -> List[List[int]]:
3
        self.ans = []
4
        self.nums = nums
5
        for k in range(len(nums) + 1):
6
            self.backtrack(k)
7
        return self.ans
8
        
9
    def backtrack(self, k, first=0, curr=[]):
10
        
11
        if len(curr) == k:
12
            self.ans.append(curr.copy())
13
            return
14
        
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.


xxxxxxxxxx
22
1
class 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.ans
8
        
9
    def backtrack(self, k, first=0, curr=[]):
10
        
11
        if len(curr) == k:
12
            self.ans.append(curr.copy())
13
            return
14
        
15
        for i in range(first, len(self.nums)):
16
            
17
            if i > first and self.nums[i] == self.nums[i-1]:
18
                continue
19
            
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.


xxxxxxxxxx
16
1
class Solution:
2
    def permute(self, nums: List[int]) -> List[List[int]]:
3
        self.ans = []
4
        self.nums = nums
5
        self.backtrack(nums)
6
        return self.ans
7
    
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.


xxxxxxxxxx
20
1
class 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.ans
7
    
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
                continue
17
            
18
            curr.append(nums[i])
19
            self.backtrack(nums[:i] + nums[i+1:], curr)
20
            curr.pop()

(13) Letter Combinations

Leetcode 17.


xxxxxxxxxx
33
1
class 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.ans
20
    
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