Backtracking

Here are some of the best backtracking interview questions.

Letter Combinations of a Phone Number and Generate Parentheses are both great interview questions. Also make sure you are able to write code to generate permutations / subsets (combinations), those are great backtracking exercises too.

Letter Combinations of a Phone Number

Generate Parentheses

Permutations

Subsets

Word Search

17. Letter Combinations of a Phone Number

leetcode.com/problems/letter-combinations-of-a-phone-number/

17. Letter Combinations of a Phone Number

Medium

4859463Add to ListShare

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = "" Output: []

Example 3:

Input: digits = "2" Output: ["a","b","c"]

Constraints:

0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].

Solution

Approach 1: Backtracking

Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.

Here is a backtrack function backtrack(combination, next_digits) which takes as arguments an ongoing letter combination and the next digits to check.

If there is no more digits to check that means that the current combination is done.
If there are still digits to check :
- Iterate over the letters mapping the next available digit.
  - Append the current letter to the current combination combination = combination + letter.
  - Proceed to check next digits : backtrack(combination + letter, next_digits[1:]).

class Solution {
  Map<String, String> phone = new HashMap<String, String>() {{
    put("2", "abc");
    put("3", "def");
    put("4", "ghi");
    put("5", "jkl");
    put("6", "mno");
    put("7", "pqrs");
    put("8", "tuv");
    put("9", "wxyz");
  }};

  List<String> output = new ArrayList<String>();

  public void backtrack(String combination, String next_digits) {
    // if there is no more digits to check
    if (next_digits.length() == 0) {
      // the combination is done
      output.add(combination);
    }
    // if there are still digits to check
    else {
      // iterate over all letters which map 
      // the next available digit
      String digit = next_digits.substring(0, 1);
      String letters = phone.get(digit);
      for (int i = 0; i < letters.length(); i++) {
        String letter = phone.get(digit).substring(i, i + 1);
        // append the current letter to the combination
        // and proceed to the next digits
        backtrack(combination + letter, next_digits.substring(1));
      }
    }
  }

  public List<String> letterCombinations(String digits) {
    if (digits.length() != 0)
      backtrack("", digits);
    return output;
  }
}

Complexity Analysis

Time complexity : \mathcal{O}(3^N \times 4^M) where N is the number of digits in the input that maps to 3 letters (e.g. 2, 3, 4, 5, 6, 8) and M is the number of digits in the input that maps to 4 letters (e.g. 7, 9), and N+M is the total number digits in the input.
Space complexity : \mathcal{O}(3^N \times 4^M) since one has to keep 3^N \times 4^M solutions.

22. Generate Parentheses

leetcode.com/problems/generate-parentheses/

Medium

6571300Add to ListShare

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1 Output: ["()"]

Constraints:

1 <= n <= 8

Approach 1: Brute Force

Intuition

We can generate all 2^{2n} sequences of '(' and ')' characters. Then, we will check if each one is valid.

Algorithm

To generate all sequences, we use a recursion. All sequences of length n is just '(' plus all sequences of length n-1, and then ')' plus all sequences of length n-1.

To check whether a sequence is valid, we keep track of balance, the net number of opening brackets minus closing brackets. If it falls below zero at any time, or doesn't end in zero, the sequence is invalid - otherwise it is valid.

Complexity Analysis

Time Complexity : O(2^{2n}n). For each of 2^{2n} sequences, we need to create and validate the sequence, which takes O(n) work.
Space Complexity : O(2^{2n}n). Naively, every sequence could be valid. See Approach 3 for development of a tighter asymptotic bound.

Approach 2: Backtracking

Intuition and Algorithm

Instead of adding '(' or ')' every time as in Approach 1, let's only add them when we know it will remain a valid sequence. We can do this by keeping track of the number of opening and closing brackets we have placed so far.

We can start an opening bracket if we still have one (of n) left to place. And we can start a closing bracket if it would not exceed the number of opening brackets.

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, "", 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, String cur, int open, int close, int max){
        if (cur.length() == max * 2) {
            ans.add(cur);
            return;
        }

        if (open < max)
            backtrack(ans, cur+"(", open+1, close, max);
        if (close < open)
            backtrack(ans, cur+")", open, close+1, max);
    }
}

Complexity Analysis

Our complexity analysis rests on understanding how many elements there are in generateParenthesis(n). This analysis is outside the scope of this article, but it turns out this is the n-th Catalan number \dfrac{1}{n+1}\binom{2n}{n}, which is bounded asymptotically by \dfrac{4^n}{n\sqrt{n}}.

Time Complexity : O(\dfrac{4^n}{\sqrt{n}}). Each valid sequence has at most n steps during the backtracking procedure.
Space Complexity : O(\dfrac{4^n}{\sqrt{n}}), as described above, and using O(n) space to store the sequence.

Approach 3: Closure Number

Intuition

To enumerate something, generally we would like to express it as a sum of disjoint subsets that are easier to count.

Consider the closure number of a valid parentheses sequence S: the least index >= 0 so that S[0], S[1], ..., S[2*index+1] is valid. Clearly, every parentheses sequence has a unique closure number. We can try to enumerate them individually.

Algorithm

For each closure number c, we know the starting and ending brackets must be at index 0 and 2*c + 1. Then, the 2*c elements between must be a valid sequence, plus the rest of the elements must be a valid sequence.

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        if (n == 0) {
            ans.add("");
        } else {
            for (int c = 0; c < n; ++c)
                for (String left: generateParenthesis(c))
                    for (String right: generateParenthesis(n-1-c))
                        ans.add("(" + left + ")" + right);
        }
        return ans;
    }
}

Complexity Analysis

Time and Space Complexity : O(\dfrac{4^n}{\sqrt{n}}). The analysis is similar to Approach 2.

46. Permutations

leetcode.com/problems/permutations/

Medium

4956120Add to ListShare

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1] Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1] Output: [[1]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Solution

Approach 1: Backtracking

Here is a backtrack function which takes the index of the first integer to consider as an argument backtrack(first).

If the first integer to consider has index n that means that the current permutation is done.
Iterate over the integers from index first to index n - 1.
- Place i-th integer first in the permutation, i.e. swap(nums[first], nums[i]).
- Proceed to create all permutations which starts from i-th integer : backtrack(first + 1).
- Now backtrack, i.e. swap(nums[first], nums[i]) back.

1 / 14

class Solution {
  public void backtrack(int n,
                        ArrayList<Integer> nums,
                        List<List<Integer>> output,
                        int first) {
    // if all integers are used up
    if (first == n)
      output.add(new ArrayList<Integer>(nums));
    for (int i = first; i < n; i++) {
      // place i-th integer first 
      // in the current permutation
      Collections.swap(nums, first, i);
      // use next integers to complete the permutations
      backtrack(n, nums, output, first + 1);
      // backtrack
      Collections.swap(nums, first, i);
    }
  }

  public List<List<Integer>> permute(int[] nums) {
    // init output list
    List<List<Integer>> output = new LinkedList();

    // convert nums into list since the output is a list of lists
    ArrayList<Integer> nums_lst = new ArrayList<Integer>();
    for (int num : nums)
      nums_lst.add(num);

    int n = nums.length;
    backtrack(n, nums_lst, output, 0);
    return output;
  }
}

Complexity Analysis

Time complexity : \mathcal{O}(\sum_{k = 1}^{N}{P(N, k)}) where P(N, k) = \frac{N!}{(N - k)!} = N (N - 1) ... (N - k + 1) is so-called k-permutations_of_n, or partial permutation.

Here first + 1 = k for the expression simplicity. The formula is easy to understand : for each k (each first) one performs N(N - 1) ... (N - k + 1) operations, and k is going through the range of values from 1 to N (and first from 0 to N - 1).

Let's do a rough estimation of the result : N! \le \sum_{k = 1}^{N}{\frac{N!}{(N - k)!}} = \sum_{k = 1}^{N}{P(N, k)} \le N \times N!, i.e. the algorithm performs better than \mathcal{O}(N \times N!) and a bit slower than \mathcal{O}(N!).