Backtracking

Backtracking

Definitions

I found a video that gave 5 algorithms that are most frequently used in interview. The video agrees with AlgoMonster or Jiuzhang. BFS and DFS are still the most frequently used, followed by Dynamic Programming and Backtracking. The next one is the class of two pointer (oppposite direction, sliding window, fast and slow). I have dealt with the first and the last. This time, I tackle Backtracking.

Backtracking is a fancy name for improved brute-force algorithm. It attempts to check every candidate to find the correct solution, and do not check any candidate twice. That is the first improvement. The second improvement is making use of problem constraint(s) to abandon a candidate the moment it cannot possibly be completed to a valid solution.

Backtracking is often implemented with recursion and nested helper function.

The idea is intuitive, it is the problems that give the interviewees nightmare.

Problems

1. Subsets

Intuition

My first solution was a dynamic programming one (accidentally). It can be observed that starting with an empty set, I can create the power set up to an element by adding that element to each copy of existing subsets. In other words, the number of subsets doubles with every iteration. That was an awful explanation: an image will be better:

This resulted in a good solution, but not the backtracking solution.

For the backtracking solution, at each iteration, for each current subset, I need to account for the choice to include that element, and the choice not to include it. There are \(2\) choices at each elements for \(n\) elements, hence the \(2^n\) part in runtime complexity. To achieve this, I need to define a new helper function that maintain a current subset, iteratively add an element into that subset, pop it out and then continue.

There can be a follow-up question: “What if the input array does not necessarily contain only distinct elements?” For this question, the decision to be made becomes whether to include one or more instances of a number or not. Actually, that’s follow-up question is Subsets II.

Algorithm

For the backtracking solution: 1. Parameters are pointer k to the current position in the array and also being the return constraint (return when k equal the length of the array) and a subset represented as an array sol. 2. At each call, iterate over the subarray from k with a for loop: 1. Append the element from the array into sol 2. Append a copy of sol in the result array (the result array will be an array of arrays). 3. Call the function again on i+1 with i the current position. 4. Pop sol which is equivalent to backtrack. The for loop will naturally direct the function to the next candidate. 3. Call the recursive function and return res.

Complexity

• Time complexity: \(O(n \times 2^{n})\) for both. I have to generate all subsets and then copy them into output list.

• Space complexity: \(O(n \times 2^{n})\) for dynamic programming, \(O(n)\) for backtracking.

Code

Dynamic programming

from typing import List

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

        for num in nums:
            for i in range(len(result)):
                subset = result[i][:]
                subset.append(num)
                result.append(subset)
        return result

More “template” backtracking

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subsets = []
        self._backtrack(nums, 0, subsets, [])
        return subsets
    
    def _backtrack(self, nums, current, subsets, subset):
        if current >= len(nums):
            subsets.append(subset.copy())
            return
        
        subset.append(nums[current])
        self._backtrack(nums, current + 1, subsets, subset)
        subset.pop()

        while current + 1 < len(nums) and nums[current] == nums[current + 1]:
            current += 1
        self._backtrack(nums, current + 1, subsets, subset)

Backtracking making use of for loop to avoid a second recursive call.

from typing import List

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

        def backtrack(k, sol):
            if k == len(nums):
                return
            
            for i in range(k, len(nums)):
                sol.append(nums[i])
                res.append(sol[:])
                backtrack(i+1, sol)
                sol.pop()
        backtrack(0, [])
        return res

2. Combination Sum

Intuition

Very similar to Subsets if you ask me (I mean, they are all backtracking). As I know that this is a backtracking problem, the focus should be on designing the backtracking helper function.

For the parameters, I obviously need curSum and combination to keep track of the current sum and current combination. To iteratively add element from candidates into combination, I will use a for loop (I said it is less obvious, but hey, I find it useful and don’t need to wait for anyone to tell me when I can use for loop in recursion). The question then can be focused on the for loop. The end is obvious: the end of the array. How about the start? It is redundant to start at the beginning every time, so I should have a current parameter as starting point for the for loop. And different from Subsets I don’t want to increment every time as an element can appear more than once.

Algorithm

For helper function: 1. Base cases: current goes pass the length (just return) and curSum == target (append and return) 2. Recursion: For every element starting from current: 1. Append element to combination. 2. Call the helper function. 3. Backtrack by popping combination. 3. Call the helper function and return.

Complexity

Define

\(t\): target

\(n\): length of candidates

\(m\): minimum value in candidates

• Time complexity: \(O(n^{(\frac{t}{m}+1)})\) - The number of all possible combinations of candidates.

• Space complexity: \(O(\frac{t}{m})\) - The maximum depth of the recursive call stack.

Code

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

        def backtrack(combination, current, curSum):
            # Base cases
            if current >= len(candidates):
                return

            if curSum >= target:
                if curSum == target:
                    combinations.append(combination.copy())
                return
            
            # Recursion
            for i in range(current, len(candidates)):
                combination.append(candidates[i])
                backtrack(combination, i, curSum + candidates[i])
                combination.pop()
        
        backtrack([], 0, 0)
        return combinations

3. Permutations

Intuition

A permutation, at least as defined here, is an array containing all elements from the original array, but order matters. To build such an array, I start with modifying the solution for combinations. The first change I made was removing current_index - now I need to add every element. However, simply adding the element led to max recursion depth. Okay, I needed to add the length of the array as safe point. Now I receive a list full of the first element. Okay, it was better to add a set to check for repeating element. And suddenly I was done.

I can do away with the set and just use the permutation candidate to check for repeating element, trading sapce for time. Well, I chose time.

Algorithm

For the helper function:

1. Parameters: a permutation candidate and the set containing elements of that candidate for faster checking.
2. Base case: the length of the candidate equals that of the original array (append and return).
3. Recursive case: Iterate through nums:
   1. If the current element is not yet in the permutation candidate, append it.
   2. Call the helper function recursively.
   3. Backtrack by popping from the array and set.
4. Call the helper function and return.

Complexity

• Time complexity: \(O(n \times n!)\): There are \(n!\) permutations for an array of length \(n\), and copy the list takes \(n\) time complexity every time. This is just an approximation, but good enough for this case given the use of a set to check for used element. The analytical complexity is more complex, and can be found here. For an interview, and especially for this implementation, \(O(n \times n!)\) is good enough.

• Space complexity: \(O(n)\): The recursive call stack, length of permu_list, and length of permu_set all point to \(n\).

Code

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

        def backtrack(permu_list, permu_set):
            if len(permu_list) == len(nums):
                permutations.append(permu_list.copy())
                return
            
            for num in nums:
                if num not in permu_set:
                    permu_list.append(num)
                    permu_set.add(num)
                    backtrack(permu_list, permu_set)
                    permu_list.pop()
                    permu_set.discard(num)

        backtrack([], set())
        return permutations

4. Letter Combinations of a Phone Number

Intuition

This was a straightforward problem. For each digit in digits, I iterate through the corresponding letters stored inside a dictionary, append it, continue, and then pop it to append another one. Simple backtracking.

Approach

For the helper function 1. Parameters: letters, array containing the letters and current, pointer to the position of the digit in digits. 2. Base case: When current >= len(digits), I have reached the end so I should return. 3. Recursive case: for every letter in the current string corresponding to the current digit 1. Append that letter to letters. 2. Call the helper function again. 3. Pop the letter out to move on the next one. 4. Call the helper function and return.

Complexity

• Time complexity: \(O(n \times 4^{n})\): I need to iterate through digits, and for every digit, I need to iterate through maximum 4 cases. That together makes the \(4^{n}\) part. Turning the array to string to append it takes \(O(n)\) times, and it is done inside the recursive loop, so they are multiplied together.

• Space complexity: \(O(n)\): The height of the recursive call stack.

Code

import string

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # Edge case
        if not digits:
            return []

        lower_alphabet = string.ascii_lowercase
        digitToLetter = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
        result = []
        
        def backtrack(letters, current):
            # Base case
            if current >= len(digits):
                result.append(''.join(letters))
                return
            
            current_digit = digits[current]
            for letter in digitToLetter[current_digit]:
                letters.append(letter) 
                backtrack(letters, current + 1)
                letters.pop()
        
        backtrack([], 0)
        return result

5. Combinations

Intuition

Another day, another backtracking problem. The thing that I need to pay attention to is base case. Of course, when the length of the list reaches the requirement, I need to return. However, as I iteratively add number to the array left to right, when I hit a point where the number of elements left are smaller than the number of elements I need more, I can return right away.

Algorithm

For the helper function 1. Parameters: combination, the array of current combination, and current_num, the current number to be appended to the array. 2. Base cases: length of combination equals that of the array (append and return). 3. Recursion: First, calculate the number of nodes needed more, the number of remaining node, and the number of available nodes. The number of available nodes will be used as a safeguard in the for loop to abandon paths that do not lead to solution. Afterwards, it is a for loop with backtracking as always.

Complexity

• Time complexity: \(O(\frac{n!}{(k-1)!(n-k)!})\): First, for those who paid attention during maths lessons, the number of combinations i.e., paths here is \(O(\frac{n!}{k!(n-k)!})\). There are at most \(k\) nodes in a path, but the actual number is way smaller because there are overlaps (consider 1 in \(20 \choose 6\)). However, the actual number is irrelevant as there is a \(O(k)\) work of copying the array at each leaf. Hence, the time complexity \(O(\frac{k\times n!}{k!(n-k)!}) = O(\frac{n!}{(k-1)!(n-k)!})\).

• Space complexity: \(O(k)\): Just the size of the recursive call stack.

Code

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []

        def backtrack(combination, current_num):
            print(combination)
            # Base case
            if len(combination) == k:
                result.append(combination[:])
                return
            
            need = k - len(combination)
            remain = n - current_num + 1
            available = remain - need
            
            # Recursion
            for num in range(current_num, current_num + available + 1):
                combination.append(num)
                backtrack(combination, num + 1)
                combination.pop()
                
        
        backtrack([], 1)
        return result

6. N-Queens

Intuition

The most notorious problem in the world of backtracking. Belong to none of the Combination/Permutation/Subset pattern.

I struggled to come up with a procedure to check the positions effectively. I know that first, I must put a queen on the board. Then I need to check for the diagonals, the row, and the column. For the row, because I increment, I can affort to not check the row. But I need to check the columns and the column.

The incredible intuition is the fact that one diagonal can be represented by the sum of row and column, the other by the difference between row and column. With this, the columns and diagonals each can be represented by a single number, and that number can be used to check whether a queen has occupied it or not. Three sets can be used for this.

Approach

Initialize the sets of column and both diagonals + the board for insertion and the return list. For the helper function: 1. Parameter: the current row. 2. Base case: When row passes the board size, append the board to return list. 3. Recursion: For each column in the board: 1. If the corresponding position has been taken by a queen through the column or digonal, do nothing. 2. Else, try putting a queen there and add the position to the sets. 3. Call the helper function on the next row. 4. Backtrack by resetting the position and remove element from the sets. 4. Call the helper function and return result list.

Complexity

• Time complexity: \(O(n!)\): The first queen has \(n\) options on the first row, the second queen has \(n-1\) (pessimistically, usually just \(n-2\) or \(n-3\)) options on the second row, and so on.

• Space complexity: \(O(n!)\): The number of possible boards corresponds to the number of possible solutions stored inside the result list.

Code

from typing import List

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        column = set()
        posDiag = set()
        negDiag = set()

        result = []
        board = [['.' for _ in range(n)] for _ in range(n)]

        def backtrack(row):
            # Base case
            if row == n:
                final_board = [''.join(row) for row in board]
                result.append(final_board)
                return
            
            # Recursion
            for col in range(n):
                if col in column or (row + col) in posDiag or (row - col) in negDiag:
                    continue

                column.add(col)
                posDiag.add(row + col)
                negDiag.add(row - col)
                board[row][col] = 'Q'

                backtrack(row + 1)

                column.remove(col)
                posDiag.remove(row + col)
                negDiag.remove(row - col)
                board[row][col] = '.'
        
        backtrack(0)
        return result