Hasuer's Studio.

22. Pattern Backtracking

Grokking Interview Pattern Interview
Word count: 6.3kReading time: 39 min
2024/05/22

Introduction to Backtracking Pattern

Backtracking

Backtracking is an algorithmic technique that uses brute-force approach to solve a problem.

Brute-force approach states that for any problem, we should try out all possible solutions and pick up those solutions that satisfy the problem constraints.

In backtracking, we build a solution incrementally and follow the approach that if the current solution can’t lead to a valid solution, abandon it and backtrack (or go back) to try another solution. Because of this, recursion becomes a suitable technique for solving backtracking problems.

Dynamic Programming (DP) uses a similar approach where we try out all possible solutions (using Memoization) to pick up the most optimized solution. DP is used to solve optimization problems; backtracking, on the other hand, is mostly used when multiple valid solutions are possible for a problem.

An Example

Let’s understand backtracking with an example.

Imagine we want to plant, in a straight line, three fruit trees Apple, Orange, and Mango. What are the possible ways these trees can be planted? The only restriction we have is that Apple and Orange trees can’t be placed next to each other.

Following a brute-force approach, we can find all possible combinations in which the three trees can be placed and pick those that fulfill the given constraint.

Let’s try finding all the possible arrangements.

The first tree can be of any kind, Apple, Orange, or Mango. If our first tree is Apple, the second tree can be Orange or Mango. If we place Orange as our second tree, then our constraint is not fulfilled (which was not to place Apple and Orange together). Hence it is not a valid arrangement; therefore, we go back (i.e., backtrack) and place Mango as our second tree.

Now, we can place Orange in the third place; this arrangement fulfills the problem constraint.

The following diagram shows all possible arrangements:

From the above diagram, we can clearly see that the two valid arrangements are: [Apple, Mango, Orange] and [Orange, Mango, Apple].

This approach of evaluating all possible solutions, going back whenever we see that a certain constraint can’t be met, and trying out other possible solutions is called backtracking.

Let’s solve some more problems to develop a deeper understanding of backtracking.

Combination Sum

Top Interview 150 | 39. Combination Sum Design Gurus

Problem Statement

Given an array of distinct positive integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Example 1:

1
2
3
Input: candidates = [2, 3, 6, 7], target = 7  
Output: [[2, 2, 3], [7]]  
Explanation: The elements in these two combinations sum up to 7.

Example 2:

1
2
3
Input: candidates = [2, 4, 6, 8], target = 10  
Output: [[2,2,2,2,2], [2,2,2,4], [2,2,6], [2,4,4], [2,8], [4,6]]    
Explanation: The elements in these six combinations sum up to 10.

Constraints:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All elements of candidates are distinct.
  • 1 <= target <= 40

Solution

This problem is quite similar to the example discussed in the previous lesson (placing apple, orange, and mango trees).

We can follow the brute-force approach to incrementally build the solution.

If, at any time, we find out that the current solution can’t lead to a valid combination, we will abandon it and backtrack to try the remaining solutions.

Let’s try this approach on the following input: Candidates: [3, 4, 5], Target: 9

Here are the number of steps in our algorithm:

  1. We will start with an empty set. This also means that the sum of the elements in the set is zero.
  2. We can try adding all three numbers separately in the set. This will give us three sets: [3], [4], [5].
  3. Let’s take set [3], since the sum of its elements is less than the Target (=9), we will try adding more numbers to it.
  4. We can add all three numbers again to generate new sets. We can add ‘3’ again, as each number can be added multiple times.
  5. After adding all numbers separately to the set [3], we will get the following sets: [3, 3], [3, 4], [3, 5]. We can see, each set has a sum less than the target.
  6. We can now, repeat the same process as described in step-4.
    • For [3, 3]: Adding ‘3’ will give us a valid solution [3, 3, 3] having a sum equal to the target. Adding ‘4’ and ‘5’ will give us a sum which is greater than the target. Therefore, we can stop the search here for this set, as adding any additional number will not produce a correct solution.
    • For [3, 4]: We will add ‘4’ or ‘5’ to it, which will give us a sum greater than the target. We will stop our search here for this set.
    • For [3, 5]: We can only add ‘5’ to it, which does not produce a valid solution.
  7. Similar approach can be applied to other sets.
  8. In the end, we can see that the valid solutions are: [3, 3, 3] and [4, 5].

Code

The basic idea is to start with an empty combination and iterate through the candidates array, adding each candidate to the current combination and recursively calling the function with the updated combination and the remaining target. If the target becomes 0, we add the current combination to the result list. If the target becomes negative, we backtrack and remove the last added candidate from the combination.

The function combinationSum takes in two parameters, an array of distinct integers candidates and a target integer target, and returns a list of all unique combinations of candidates where the chosen numbers sum to target. The function starts by defining the function backtrack(candidates, start, target, comb, res). This function takes five parameters, candidates, start, target, comb, and res:

  • candidates is the array containing candidate elements.
  • start is the starting index of the candidates array.
  • target is the remaining target.
  • comb is the current combination.
  • res is the final result list.

The backtrack function uses recursion to find the combinations. The base case for the recursion is if the target is 0. When the target is 0, that means we have found a valid combination and we append a copy of the current combination to the result list. It then iterates through the candidates array starting from the given index. If the current candidate is greater than the remaining target, it skips the current candidate and move on to the next. If the current candidate is less than the remaining target, it adds the current candidate to the current combination, recursively calls the function with the updated combination and remaining target, and then backtracks by removing the last added candidate from the combination.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution(object):
    def combinationSum(self, candidates, target):
        res = []  # To store the final result
        self.backtrack(candidates, 0, target, [], res)
        return res

    def backtrack(self, candidates, start, target, comb, res):
        # If target is 0, we have found a valid combination
        if target == 0:
            # Append a copy of the current combination to the result list
            res.append(list(comb))
            return
        # Iterate through the candidates array starting from the given index
        for i in range(start, len(candidates)):
            # If the current candidate is greater than the remaining target, move on to the next
            if target < candidates[i]:
                continue
            # Add the current candidate to the current combination
            comb.append(candidates[i])
            # Recursively call the function with the updated combination and remaining target
            self.backtrack(candidates, i, target - candidates[i], comb, res)
            # Backtrack by removing the last added candidate from the combination
            comb.pop()


def main():
    # Test case 1
    candidates = [2, 3, 6, 7]
    target = 7
    s = Solution()
    print(s.combinationSum(candidates, target))  # expected output: [[2, 2, 3], [7]]

    # Test case 2
    candidates = [2, 3, 5]
    target = 8
    s = Solution()
    print(
        s.combinationSum(candidates, target)
    )  # expected output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

    # Test case 3
    candidates = []
    target = 8
    s = Solution()
    print(s.combinationSum(candidates, target))  # expected output: []

    # Test case 4
    candidates = [5, 10, 15]
    target = 20
    s = Solution()
    print(
        s.combinationSum(candidates, target)
    )  # expected output: [[5,5,5,5], [5,5,10], [5,15], [10,10]]

    # Test case 5
    candidates = [2, 4, 6, 8]
    target = 10
    s = Solution()
    print(
        s.combinationSum(candidates, target)
    )  # expected output: [[2,2,2,2,2], [2,2,2,4], [2,2,6], [2,4,4], [2,8], [4,6]]

    # Test case 6
    candidates = [2, 3, 5]
    target = 0
    s = Solution()
    print(s.combinationSum(candidates, target))  # expected output: [[]]


main()

Time Complexity

This algorithm has a time complexity of O(N^(T/M + 1)), where is N the total number of elements in the candidates array, T is the target value, and M is the smallest value among the candidates. This is because the execution of the backtracking is similar to a DFS traversal of an n-ary tree. So, the time complexity would be the same as the number of nodes in the n-ary tree. This can be seen in the above diagram.

Each node can call the backtrack function a maximum of N times, i.e., the total number of candidates. The maximal depth of the n-ary tree would be T/M, where we keep on adding the smallest element to the combination. As we know, the maximal number of nodes in N-ary tree of T/M height would be N^(T/M + 1), hence the time complexity is O(N^(T/M + 1)).

Space Complexity

Ignoring the space needed for the output array, the space complexity will be O(T/M) because at any time, we can pile up to T/M recursive calls of the backtrack function; this will happen when we keep on adding the smallest element to the combination. As a result, the space overhead of the recursion is O(T/M).

Top Interview 150 | 79. Word Search Design Gurus

类似 这道题

Problem Statement

Given an m x n grid of characters board and a string word, return true if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:
Input: word=”ABCCED”, board:

1
2
3
{ 'A', 'B', 'C', 'E' },
{ 'S', 'F', 'C', 'S' },
{ 'A', 'D', 'E', 'E' }

Output: true Explanation: The word exists in the board:
-> { ‘A’, ‘B’, ‘C’, ‘E’ },
-> { ‘S’, ‘F’, ‘C’, ‘S’ },
-> { ‘A’, ‘D’, ‘E’, ‘E’ }

Example 2:
Input: word=”SEE”, board:

1
2
3
{ 'A', 'B', 'C', 'E' },
{ 'S', 'F', 'C', 'S' },
{ 'A', 'D', 'E', 'E' }

Output: true Explanation: The word exists in the board:
-> { ‘A’, ‘B’, ‘C’, ‘E’ },
-> { ‘S’, ‘F’, ‘C’, ‘S’ },
-> { ‘A’, ‘D’, ‘E’, ‘E’ }

Constraints:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

Solution

The basic approach to solving the word search problem using backtracking is to start at the first character of the word and check all 8 adjacent cells in the grid to see if any of them match the next character of the word. If a match is found, mark the cell as visited and recursively check the next character of the word in the adjacent cells of the newly visited cell. If the entire word is found, return true. If no match is found, backtrack to the previous cell and try a different path. Repeat this process until the entire grid has been searched or the word is found.

Code

This function takes a 2D list board and a string word as input, and returns True if the word can be found in board and False otherwise. It uses a helper function dfs which takes 4 additional parameters: i and j are the current coordinates of the cell that is being visited, k is the index of the current character of the word being matched, and board and word are the inputs passed to the main function.

The dfs function uses a helper variable tmp to store the current value of the cell before it is marked as visited. This is done so that we can backtrack later. It then uses recursion to check if the next character of the word exists in the 4 adjacent cells, and it will mark the cell as visited and move to next index of the word by incrementing k by 1. If the next character is found, the function returns true, if not it backtracks to the previous cell, and continues the search in different path. If the entire word is found, the function returns True, otherwise it returns False after searching the entire grid.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class Solution:
    def dfs(self, board, word, i, j, k):
        # check if current coordinates are out of grid or the current cell doesn't match the current character of the word
        if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]:
            return False
        # check if we have reached the end of the word
        if k == len(word) - 1:
            return True
        # mark the current cell as visited by replacing it with '/'
        tmp, board[i][j] = board[i][j], '/'
        # check all 4 adjacent cells recursively
        res = self.dfs(board, word, i + 1, j, k + 1) or \
              self.dfs(board, word, i - 1, j, k + 1) or \
              self.dfs(board, word, i, j + 1, k + 1) or \
              self.dfs(board, word, i, j - 1, k + 1)
        # backtrack by replacing the current cell with its original value
        board[i][j] = tmp
        return res

    def exist(self, board, word):
        for i in range(len(board)):
            for j in range(len(board[0])):
                # start the search from every cell
                if board[i][j] == word[0]: # 这一行是我加的，可以减少搜索空间
                    if self.dfs(board, word, i, j, 0):
                        return True
        return False


def main():
    sol = Solution()
    # Test Case 1
    board = [
        ['A', 'B', 'C', 'E'],
        ['S', 'F', 'C', 'S'],
        ['A', 'D', 'E', 'E']
    ]
    word = "ABCCED"
    print(sol.exist(board, word))  # expected output: True

    # Test Case 2
    board = [
        ['A', 'B', 'C', 'E'],
        ['S', 'F', 'C', 'S'],
        ['A', 'D', 'E', 'E']
    ]
    word = "SEE"
    print(sol.exist(board, word))  # expected output: True

    # Test Case 3
    board = [
        ['A', 'B', 'C', 'E'],
        ['S', 'F', 'C', 'S'],
        ['A', 'D', 'E', 'E']
    ]
    word = "ABCB"
    print(sol.exist(board, word))  # expected output: False

    # Test Case 4
    board = [['a', 'a']]
    word = "aaa"
    print(sol.exist(board, word))  # expected output: False

    # Test Case 5
    board = [['a']]
    word = "a"
    print(sol.exist(board, word))  # expected output: True

    # Test Case 6
    board = [
        ['a', 'b', 'c', 'd', 'e'],
        ['f', 'g', 'h', 'i', 'j'],
        ['k', 'l', 'm', 'n', 'o'],
        ['p', 'q', 'r', 's', 't'],
        ['u', 'v', 'w', 'x', 'y'],
        ['z', 'a', 'b', 'c', 'd']
    ]
    word = "abcde"
    print(sol.exist(board, word))  # expected output: True

    # Test Case 7
    board = [
        ['a', 'b', 'c', 'd', 'e'],
        ['f', 'g', 'h', 'i', 'j'],
        ['k', 'l', 'm', 'n', 'o'],
        ['p', 'q', 'r', 's', 't'],
        ['u', 'v', 'w', 'x', 'y'],
        ['z', 'a', 'b', 'c', 'd']
    ]
    word = "zabcd"
    print(sol.exist(board, word))  # expected output: True


main()

Time Complexity

The time complexity of the ‘exist’ function is O(4^n), where is n the length of the word. This is because the function uses a depth-first search (DFS) algorithm to traverse the board, and for each cell in the board, it checks all 4 adjacent cells recursively. The worst-case scenario is when the word is found in the last cell of the board, and in that case, the function will have to check all possible paths from the starting cell to the last cell, which is 4^n possible paths.

Space Complexity

The space complexity of the exist function is O(n), where n is the length of the word. This is because the function uses a DFS algorithm, and the maximum depth of the recursion tree is n. In other words, the maximum number of function calls that will be stored on the call stack at any point in time is n.

Sudoku Solver

37. Sudoku Solver Design Gurus

Problem Statement

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  • Each of the digits 1-9 must occur exactly once in each row.
  • Each of the digits 1-9 must occur exactly once in each column.
  • Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The ‘.’ character indicates empty cells.

Example 1:
Input:

1
2
3
4
5
6
7
8
9
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}

Output:

1
2
3
4
5
6
7
8
9
{'5'', '3'', '4'', '6'', '7'', '8'', '9'', '1'', '2''},
{'6'', '7'', '2'', '1'', '9'', '5'', '3'', '4'', '8''},
{'1'', '9'', '8'', '3'', '4'', '2'', '5'', '6'', '7''},
{'8'', '5'', '9'', '7'', '6'', '1'', '4'', '2'', '3''},
{'4'', '2'', '6'', '8'', '5'', '3'', '7'', '9'', '1''},
{'7'', '1'', '3'', '9'', '2'', '4'', '8'', '5'', '6''},
{'9'', '6'', '1'', '5'', '3'', '7'', '2'', '8'', '4''},
{'2'', '8'', '7'', '4'', '1'', '9'', '6'', '3'', '5''},
{'3'', '4'', '5'', '2'', '8'', '6'', '1'', '7'', '9''}

Explanation: The given output is the only valid Sudoku solution.

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or ‘.’.
  • It is guaranteed that the input board has only one solution.

Solution

Sudoku is a popular puzzle game that involves filling in a 9x9 grid with numbers such that each column, each row, and each of the nine 3x3 sub-grids that compose the grid contains all of the digits from 1 to 9. One way to solve a sudoku puzzle is by using backtracking, which is a form of brute-force search.

Here are the steps to solve a sudoku puzzle using backtracking:

  1. Start with an empty 9x9 grid and fill in the numbers that are given in the puzzle.
  2. From left to right and top to bottom, find the first empty cell (denoted by a .) in the grid.
  3. Try out every number from 1 to 9 as a possible solution for the empty cell.
  4. Before filling in a number, check if it is a valid solution by checking if the number is already present in the same row, column, or 3x3 sub-grid.
  5. If the number is valid, fill it in the cell and recursively call the function to move to the next empty cell.
  6. If the number is not valid, backtrack to the previous state and try a different number.
  7. If a valid solution is found, return true. If no solution is found, return false.
  8. If the function returns true, the grid is filled with a valid solution. Else, the puzzle is unsolvable.

Code

The function solveSudoku starts by iterating through the board and checking for empty cells represented by ‘.’ character. When an empty cell is found, the function tries every number from 1-9 by using a nested loop. Before filling the cell with a number, the function checks if the number is valid in the current cell by using the helper function isValid. The function isValid checks if the same number is already present in the same row, column or 3x3 box. If the number is valid, the cell is filled with the number and the function recursively calls itself to solve the rest of the board.

If the current number doesn’t lead to a solution, the function backtracks by emptying the cell and trying the next number. If all the numbers have been tried and none of them lead to a solution, the function returns false. If the board is completely filled, the function returns true, indicating that a solution has been found.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution:
    # Helper function to check if a given number is valid in the current cell
    def isValid(self, board, row, col, num):
        # Check if we already have the same number in the same row, col or box
        for x in range(9):
            if board[row][x] == num:
                return False  # Check if the same number is in the same row
            if board[x][col] == num:
                return False  # Check if the same number is in the same col
            if board[(row // 3) * 3 + x // 3][(col // 3) * 3 + x % 3] == num:
                return False  # Check if the same number is in the same 3x3 box
        return True

    def solveSudoku(self, board):
        for row in range(9):
            for col in range(9):
                if board[row][col] == '.':  # If we find an empty cell
                    for num in range(1, 10):  # Try every number from 1-9
                        if self.isValid(board, row, col, str(num)):  # Check if the number is valid in the current cell
                            board[row][col] = str(num)  # If it is valid, fill the cell with the number
                            if self.solveSudoku(board):  # Recursively call the function to solve the rest of the board
                                return True
                            else:  # If the current number doesn't lead to a solution, backtrack by emptying the cell
                                board[row][col] = '.'
                    return False  # If we have tried every number and none of them lead to a solution, return false
        return True  # If the board is completely filled, return true


def main():
    sol = Solution()
    # Test case 1
    board = [['5', '3', '.', '.', '7', '.', '.', '.', '.'],
             ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
             ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
             ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
             ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
             ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
             ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
             ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
             ['.', '.', '.', '.', '8', '.', '.', '7', '9']]

    print(sol.solveSudoku(board))
    # expected output:  5 3 4 6 7 8 9 1 2 
    #                   6 7 2 1 9 5 3 4 8 
    #                   1 9 8 3 4 2 5 6 7 
    #                   8 5 9 7 6 1 4 2 3 
    #                   4 2 6 8 5 3 7 9 1 
    #                   7 1 3 9 2 4 8 5 6 
    #                   9 6 1 5 3 7 2 8 4 
    #                   2 8 7 4 1 9 6 3 5 
    #                   3 4 5 2 8 6 1 7 9
    print(board)

    # Test case 2
    board = [['8', '.', '.', '.', '.', '.', '.', '.', '.'],
             ['.', '.', '3', '6', '.', '.', '.', '.', '.'],
             ['.', '7', '.', '.', '9', '.', '2', '.', '.'],
             ['.', '5', '.', '.', '.', '7', '.', '.', '.'],
             ['.', '.', '.', '.', '4', '5', '7', '.', '.'],
             ['.', '.', '.', '1', '.', '.', '.', '3', '.'],
             ['.', '.', '1', '.', '.', '.', '.', '6', '8'],
             ['.', '.', '8', '5', '.', '.', '.', '1', '.'],
             ['.', '9', '.', '.', '.', '.', '4', '.', '.']]
    print(sol.solveSudoku(board))
    # expected output:  8 1 2 7 5 3 6 4 9 
    #                   9 4 3 6 8 2 1 7 5 
    #                   6 7 5 4 9 1 2 8 3 
    #                   1 5 4 2 3 7 8 9 6 
    #                   3 6 9 8 4 5 7 2 1 
    #                   2 8 7 1 6 9 5 3 4 
    #                   5 2 1 9 7 4 3 6 8 
    #                   4 3 8 5 2 6 9 1 7 
    #                   7 9 6 3 1 8 4 5 2
    print(board)


main()

Time Complexity

since the board size is fixed, the time complexity is O(1), as there is no variable input.

Though let’s discuss the number of operations needed: (9!)^9

Let’s consider one row where we have 9 cells to fill. There are not more than 9 possibilities for the first number to put, not more than 9×8 for the second one, not more than 9×8×7 for the third one, and so on. In total, that results in not more than (9!) possibilities for just one row; this means not more than (9!)^9 operations in total.

If we compare the brutefore and backtracking algorithms:

  • 9^81 = 1966270504755529136180759085269121162831034509442147669273154155379663911968099 for the brute force,
  • and (9!)^9 =109110688415571316480344899355894085582848000000000 for the standard backtracking, i.e. the number of operations is reduced in times!

Space Complexity

The board size is fixed, and the space is used to store the board containing 81 cells, hence the time complexity is O(1).

Factor Combinations

leetcode 会员 Design Gurus

Problem Statement

Numbers can be regarded as the product of their factors.

For example, 8 = 2 x 2 x 2 = 2 x 4.

Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Example 1:

1
2
Input: n = 8  
Output: [[2, 2, 2], [2, 4]]

Example 2:

1
2
Input: n = 20  
Output: [[2, 2, 5], [2, 10], [4, 5]]

Constraints:

  • 1 <= n <= 10^7

Solution

We can use backtracking to find all the factors of a given number .

We will start by iterating through all integers from start (2 by default) to the square root of n+1. If the current integer i divides n, we will add i to the list of current factors curr and appends this list along with the corresponding factor of n/i to the list of all factors (result). Then we can recursively call the function with n/i as the new input, i as the new start value, and curr and result as the current factors and results. After each recursive call, we have to pop the last element from curr to backtrack and find other factors.

Code

Here is what our algorithm will look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def getAllFactors(self, n, start, curr, result):
        # Iterate through all integers i from start to the square root of n + 1
        # This loop is used to find all the factors of the input number n
        for i in range(start, int(n ** 0.5) + 1):
            # If n is divisible by i, add i to the curr list of factors
            # curr is used to store the current factors being calculated
            if n % i == 0:
                curr.append(i)  # Found a factor, append it to the list of factors
                # Append the current factors and the corresponding factor of n // i to the result list
                result.append(list(curr + [n // i]))
                # Recursively call the function with n // i as the new input, i as the new start value, and curr and result as the current factors and results
                self.getAllFactors(n // i, i, curr, result)
                curr.pop()  # Pop the last element from curr to backtrack and find other factors
        return result

    def getFactors(self, n):
        return self.getAllFactors(n, 2, [], [])


# test cases
sol = Solution()
print(sol.getFactors(8))  # expected: [[2, 2, 2], [2, 4]]
print(sol.getFactors(12))  # expected: [[2, 2, 3], [2, 6], [3, 4]]
print(sol.getFactors(16))  # expected: [[2, 2, 2, 2], [2, 2, 4], [2, 8], [4, 4]]
print(sol.getFactors(20))  # expected: [[2, 2, 5], [2, 10], [4, 5]]
print(sol.getFactors(1))  # expected: []

Time Complexity

We can’t have more than factors of a number n. This means that getAllFactors can be called a maximum of times recursively. The for loop iterates a maximum of . This means that the overall time complexity is or

Space Complexity

Ignoring the space needed for the output array, the space complexity will be as we need to save only one factor while in the recursion, and our recursion tree won’t get bigger than steps.

Split a String Into the Max Number of Unique Substrings

1593. Split a String Into the Max Number of Unique Substrings Design Gurus

Problem Statement

Given a string s, return the maximum number of unique substrings that the given string can be split into.

You can split string s into any list of non-empty substrings, where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique.

A substring is a contiguous sequence of characters within a string.

Example 1:

1
2
3
Input: s = "aab"  
Output: 2  
Explanation: Two possible ways to split the given string into maximum unique substrings are: ['a', 'ab'] & ['aa', 'b'], both have 2 substrings; hence the maximum number of unique substrings in which the given string can be split is 2.

Example 2:

1
2
3
Input: s = "abcabc"  
Output: 4  
Explanation: Four possible ways to split into maximum unique substrings are: ['a', 'b', 'c', 'abc'] & ['a', 'b', 'cab', 'c'] &  ['a', 'bca', 'b', 'c'] & ['abc', 'a', 'b', 'c'], all have 4 substrings.

Constraints:

  • 1 <= s.length <= 16
  • s contains only lower case English letters.

Solution

We can use backtracking to solve this problem.

This solution uses a helper function splitAndCount which takes three arguments, the input string s, the current start position and a set set to keep track of the unique substrings that have been split so far. The maxUniqueSplit function calls the splitAndCount function to find the maximum number of unique substrings that the given string can be split into.

The splitAndCount function starts with a base case where it returns the size of the set when the current start position is equal to the length of the input string. This means that all substrings have been processed and the size of the set represents the maximum number of unique substrings.

The function then uses a for loop to iterate through all possible substrings starting from the current start position. For each substring, it checks if the substring is already in the set. If it is not, the substring is added to the set and the function is recursively called with the new start position being the end of the current substring. This continues until all possible substrings have been processed.

After the recursive call, the substring is removed from the set to backtrack. The function keeps track of the maximum number of unique substrings found so far and returns this maximum count when all substrings have been processed.

Code

Here is the code of our algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        return self.split_and_count(s, 0, set())

    def split_and_count(self, s: str, start: int, set) -> int:
        # base case, if we have reached the end of the input string, return the size of the set
        if start == len(s):
            return len(set)

        count = 0
        # loop through all substrings starting from the current start position
        for i in range(start + 1, len(s) + 1):
            string = s[start:i]
            # if the substring is not in the set, add it and recursively call the function with the new start position
            if string not in set:
                set.add(string)
                count = max(count, self.split_and_count(s, i, set))
                set.remove(string)  # remove the substring from the set and backtrack

        return count  # return the maximum count of unique substrings found


if __name__ == "__main__":
    sol = Solution()

    # Test Case 1
    input1 = "abcabc"
    output1 = sol.maxUniqueSplit(input1)
    print("maxUniqueSplit(" + input1 + ") = " + str(output1))  # Expected: 4

    # Test Case 2
    input2 = "aab"
    output2 = sol.maxUniqueSplit(input2)
    print("maxUniqueSplit(" + input2 + ") = " + str(output2))  # Expected: 2

    # Test Case 3
    input3 = "ababab"
    output3 = sol.maxUniqueSplit(input3)
    print("maxUniqueSplit(" + input3 + ") = " + str(output3))  # Expected: 4

    # Test Case 4
    input4 = ""
    output4 = sol.maxUniqueSplit(input4)
    print("maxUniqueSplit(" + input4 + ") = " + str(output4))  # Expected: 0

    # Test Case 5
    input5 = "a"
    output5 = sol.maxUniqueSplit(input5)
    print("maxUniqueSplit(" + input5 + ") = " + str(output5))  # Expected: 1

Time Complexity

We can split any given string of length n in 2^n ways. Hence the time complexity will be O(2^n).

Space Complexity

The space complexity will be O(n) as we need to save only one way of splitting the given string while in the recursion, and our recursion tree won’t get bigger than O(n) steps too.

Author：Hasuer

Link：https://hasuer.github.io/22-pattern-backtracking/index.html

Publish date：May 22nd 2024, 2:18:42 pm

Update date：May 28th 2024, 11:30:31 am

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Introduction to Backtracking Pattern
    1. 1.1. Backtracking
      1. 1.1.1. An Example
  2. 2. Combination Sum
    1. 2.1. Problem Statement
    2. 2.2. Solution
    3. 2.3. Code
    4. 2.4. Time Complexity
    5. 2.5. Space Complexity
  3. 3. Word Search
    1. 3.1. Problem Statement
    2. 3.2. Solution
    3. 3.3. Code
    4. 3.4. Time Complexity
    5. 3.5. Space Complexity
  4. 4. Sudoku Solver
    1. 4.1. Problem Statement
    2. 4.2. Solution
    3. 4.3. Code
    4. 4.4. Time Complexity
    5. 4.5. Space Complexity
  5. 5. Factor Combinations
    1. 5.1. Problem Statement
    2. 5.2. Solution
    3. 5.3. Code
    4. 5.4. Time Complexity
    5. 5.5. Space Complexity
  6. 6. Split a String Into the Max Number of Unique Substrings
    1. 6.1. Problem Statement
    2. 6.2. Solution
    3. 6.3. Code
    4. 6.4. Time Complexity
    5. 6.5. Space Complexity
Total : 41
2024
2022
2021
Interview
技术笔记 Grokking-Interview-Pattern