Backtracking

Notes and typical questions for backtracking algorithm

Notes

General code template

private void backtracking(parameters) {
    if (termination condition) {
        collect result;
        return;
    }

    for (choose items to be processed in the same level) {
        process items;
        backtracking(parameters);
        restore status;
    }
}

Permutation problems and Combination problems are very similar, differences are
- Combination use startIndex to dedup in branch direction. Permutation use used[]/Set to dedup in branch direction. Reason: [1,2] and [2,1] are the same results in combination but different results in permutation. Therefore, in each level, for loop starts from startIndex in Combination but from 0 (skip items in used[]) in permutation.

Typical Questions

Combination

Notes

Pick k or any number of items from n items w/o special requirement. The order of results does NOT matter
Handle pruning logic
- Does not satisfy the requirement: In the 1st step of each level or the for loop if the input is sorted
- Set end condition for for loop based on k value if k is a constant
Handle dedup logic if necessary
Termination condition and return; is not required for some cases because for loop itself can cover the termination condition. But I think it's still good to have it to make logic clear.
Subset problem
- It is a variation of combination problems. The key difference is that the subset problem needs to collect results in every node but the collection problem only collects results in the leaf node. Subset problem = classic collection problem under this assumption
  - No requirement for k
  - No other requirement for the result (e.g. sum=target...)
- It has another way of implementation. Pick each item or not in each level without using for loop in each level.

🧩 Unique input items & Pick each item once & `k` is a constant

Notes
- startIndex: In for loop of each level, Pass the current i+1 as startIndex for the next level so that each item can be picked only once.
- Prune
  - Set end condition for for loop based on k value
  - If necessary, do return; at the 1st step of each level if it already does not satisfy the requirement
- Time complexity: $O(n^{k})$ (This is just the number of all combinations). $k$ is the number of elements we need to collect. $n$ is the length of input candidates. Theoretically, it should be $O(C(n, k))$ . We are taking the upper limit(i.e., Big O) for easier calculation.
🌟 ⚪ LC 77. Combinations
- Make sure to prune during backtracking
- Optimal Answer. TC: $O(k*C(n,k))$ , SC: $O(k)$
⚪ LC 216. Combination Sum III
- Similar to the above one. Do pruning for 2 cases (selection & sum).
- Do NOT introduce any useless argument! For example, we can minus the sum in each level instead of having both sum and target arguments. We can use path.size() to check the termination condition instead of using another index argument.
- Optimal Answer. TC: $O(k*C(9,k))$ , SC: $O(k)$
⚪ LC 17. Letter Combinations of a Phone Number
- Use String[] to replace Map to optimize space a bit.
- Optimal Answer. $n$ is the number of digits. TC: $O(4^{n}*n)$ , SC: $O(n)$

🧩 Unique input items & Pick each item multiple times & No requirement for `k`

Notes
- startIndex: In for loop of each level, Pass the current i as startIndex for the next level so that each item can be picked up multiple times.
- Prune
  - Without sorting: Do this logic in the first step of each level
  - With sorting (Better): Put this logic into for loop to skip all other items within the same level if it already does not satisfy the requirement.
🌟 🟠 LC 39. Combination Sum
- Approach 1: Answer from Laioffer.
- Approach 2: Answer.
  - The solution can be further optimized by performing a second pruning, but the input needs to be sorted first.
  - TC: $O((t/m) * n^{t/m+1})$ . $n$ is the length of the candidates; $t$ is the target sum; $m$ is the min value in the candidates. At each step, we can select any number any number of times. The maximum depth of the recursion tree would be $t/m$ . At each level, we have n choices at max. At the end of each combination, we need to copy path into result.
  - SC: $O(t/m)$ for additional memory in the recursive function call stack.

🧩 Duplicate input items & Pick each item once & No requirement for `k`

Notes
- Dedup: Need to sort the input first & skip items if i != startIndex && input[i] == input[i-1] in for loop
- startIndex: In for loop of each level, pass, the current i+1 as startIndex for the next level, so that each item can be picked only once.
- Prune: Since the input is sorted first, this logic can be put into for loop to skip all other items within the same level if it already does not satisfy the requirement.
- Time complexity: $C(n,n)+C(n,n-1)+...+C(n,1) = 2^n$ . This is just the number of all combinations.
🌟 🟠 LC 40. Combination Sum II
- Optimal Answer.
  - TC: $O(n*2^{n})$ . For each combination, we also need to copy path into result which is $O(n)$
  - SC: $O(n)$
🌟 LC 90. Subsets II
- Optimal Answer. TC: $O(n*2^{n})$ . SC: $O(n)$
⚪ LC 491. Non-decreasing Subsequences
- A variant of the above "LC 90. Subsets II". The difference is
  - Only collect results in some nodes with size >= 2
  - Cannot sort array to do dedup because it requires subsequence. Create local used variable using Set/int[] in each level.
- Optimal Answer. TC: $O(n*2^{n})$ . SC: $O(n)$

🧩 Unique input items & Pick each item once & No requirement for `k`

🟠 LC 131. Palindrome Partitioning
- It's a variation of combination problems. Choose the place to do the partition, fix the left part, and then go to the next level to process the right side recursively
- Optimation
  - Calculate Palindrome dp[][] in advance, so we do not need to check if each substring is a Palindrome during backtracking
  - Use same StringBuilder in the same level to store the left part
- Optimal Answer.
  - TC: $O(n*2^n)$
    $2^n$ combinations: $C(n,1) + C(n,2) + ... + C(n,n) = 2^n$ . (Cut once possibilities + Cut twice possibilities +...)
    Need to copy path into result for each Combination
  - SC: $O(n^2)$
🔴 LC 93. Restore IP Addresses
- Similar to the above LC 131, it is a string partition problem. Very easy to make mistakes in implementation.
- Optimization
  - Convert input String to StringBuilder to modify it directly.
- Optimal Answer.
  - TC: $O(3^4) = O(1)$ . The IP address can contain a maximum of 4 numbers, and each number can be split in up to 3 possible ways. Therefore, the maximum depth of the search tree is 4, and each node can have up to 3 child nodes.
  - SC: $O(1)$
🌟 LC 78. Subsets
- Most classic subsets problem. See notes under Combination.
- TC: $O(n*2^{n})$ , SC: $O(n)$
  - Approach 1 with for loop
  - Approach 2 without for loop

Permutations

Notes
- Pick k (if k < n, it's a partial permutation) or any number of items from n items w/o special requirement Order of result MATTERS
- Dedup
  - Use used[] (used.length == nums.length) to dedup in tree branch direction for all permutation problems regardless of unique input or duplicate input. used[] is similar to the startIndex used in combination problems.
- Collect results in leaf nodes.

🧩 Unique input items & Pick each item once & `k` is a constant

🌟 LC 46. Permutations
- Optimal Answer, TC: $O(n * n!)$ , SC: $O(n)$

🧩 Duplicate input items & Pick each item once & `k` is a constant

Notes
- Dedup: In addition to used[] to dedup in branch direction, we also need to dedup in tree level direction. There are 2 ways.
  - Method1: Sort the array first, then skip the item if i!=0 && nums[i] == nums[i-1] && used[i-1] == false in for loop
  - Method2: Create used2[] (used2.length == value range of nums) or Set in each level, then skip the item if used2[nums[i]] or set.contains(nums[i]) in for loop.
🌟 ⚪ LC 47. Permutations II
- 👍 Approach 1 with sort: Answer.
- Approach 2 with Set : Answer.
- TC: $O(n * n!)$ , SC: $O(n)$

2D Backtracking

🌟 🟠 LC 51. N-Queens
- Time Complexity: $O(n^2 * n * n!)$ , $n^2$ for storing the result. $n$ for checking validation. $n!$ for all valid placements.
- Better solution to speed up validation,
  - Approach 1: use 3 extra boolean[], 1st for column direction. Other 2 for diagonal direction. For how to know the diagonal index in those 2 boolean[] for a given point
  In an nxn grid there are 2n - 1 diagonals going from top left corner to bottom right corner and there are 2n-1 diagonals going from top right corner to bottom left corner. The queen can run along both of these diagonal directions so we store both of them in boolean[]s. We need to map every index to both of these diagonal boolean arrays to that indexes on the same diagonal map to the same index in the boolean array as seen below: Diagonals this way / [ 0, 1, 2] [ 1, 2, 3] [ 2, 3, 4] need to map to boolean[0,1,3,4] of size 2n - 1 with the relation row + col. Diagonals this way \ [ 2, 1, 0] [ 3, 2, 1] [ 4, 3, 2] need to map to boolean[0,1,2,3,4] of size 2n - 1 with the relation row + n - col - 1.
  - Approach 2: use 3 extra Set, 1st for column direction. Other 2 for diagonal direction. For each position (r,c)
    column set: each position is encoded to c
    diagonals set in this way \ : each position is encoded to r-c
    diagonals set in this way / : each position is encoded to r+c
- Answer. TC: $O(n!)$ , SC: $O(n^2)$
  - This is not the optimal solution with validation speedup but it's more understandable.
⚪ LC 52. N-Queens II
- Trick: Use 3 sets to speed up position checking logic.
- Optimal Answer. TC: $O(n!)$ , SC: $O(n)$
🟠 LC 37. Sudoku Solver
- I come up with a solution which is different from 代码随想录. The main difference is that each level directly checks the position that needs to be visited as the next one instead of doing a traversal from board[0][0].
- Time complexity: $9^{81}$ in the worst case

Structured Generation with Constraints

LC 22. Generate Parentheses
- Optimal Answer
  - TC: $O(n*2^{2n})$ . The accurate one is actually $O(4^n/\sqrt{n})$ , this number is related to the Catalan number. It should be out of scope for interview.
  - SC: $O(n)$
🟠 LC 3481. Apply Substitutions
- Optimal Answer
  - Let $n$ be the size of replacements , $m$ be the average length of replacements value's
  - TC: $O(n+n^2*m+n*m)$ ⇒ $O(n^2*m)$
  - SC: $O(n)$

hashtagNotes

hashtagTypical Questions

hashtagCombination

hashtagNotes

hashtag🧩 Unique input items & Pick each item once & k is a constant

hashtag🧩 Unique input items & Pick each item multiple times & No requirement for k

hashtag🧩 Duplicate input items & Pick each item once & No requirement for k

hashtag🧩 Unique input items & Pick each item once & No requirement for k

hashtagPermutations

hashtag🧩 Unique input items & Pick each item once & k is a constant

hashtag🧩 Duplicate input items & Pick each item once & k is a constant

hashtag2D Backtracking

hashtagStructured Generation with Constraints

hashtagOther Backtracking Problems

Notes

Typical Questions

Combination

Notes

🧩 Unique input items & Pick each item once & `k` is a constant

🧩 Unique input items & Pick each item multiple times & No requirement for `k`

🧩 Duplicate input items & Pick each item once & No requirement for `k`

🧩 Unique input items & Pick each item once & No requirement for `k`

Permutations

🧩 Unique input items & Pick each item once & `k` is a constant

🧩 Duplicate input items & Pick each item once & `k` is a constant

2D Backtracking

Structured Generation with Constraints

Other Backtracking Problems