[Leetcode] Backtracking

Posted on | In , |

Intro

Backtracking is usually used when you have multiple solutions and you need all the solutions. if we want a best solution(optimal) that would be Dynamic Programming problem

https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)

State Space Tree

Video: https://www.youtube.com/watch?v=DKCbsiDBN6c&t=8s

Brute Force Approach: https://www.youtube.com/watch?v=vtnpzDPgaU0

  • We would like to construct an algorithm that’s capable of finding a pattern in a text
  • Keep iterating through the text and if there’s a mismatch, we shift the pattern one step to the right
  • Problem: needs to back up for every mismatch

DFS Approach

Branch and Bound

Condition: Bounding function -> kill the tree branch that is not satisfied with condition.

22. Generate Parentheses

Leetcode: https://leetcode.com/problems/generate-parentheses/description/

[Solution]

  • First must be ‘(‘, last one must be ‘)’
  • Conditions
    • Nums of ‘(‘ <= nums of ‘)’ during traversal
    • Nums of ‘(‘ or ‘)’ <= n / 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        int open = 1;
        int close = 0;
        String str = "(";
        backtrack(str, open, close, result, n * 2);
        return result;
    }
    
    public void backtrack(String str, int open, int close, List<String> list, int n) {
        if (open > n / 2 || close > n / 2){ // Condition 1
            return;
        } 
        if (open < close) { // Condition 2
            return;
        }
        if (str.length() == n) {
            list.add(str);
        }
        backtrack(str + "(", open + 1, close, list, n); // traverse left tree
        backtrack(str + ")", open, close + 1, list, n); // traverse right tree
    }
}

17. Letter Combinations of a phone number

Leetcode: https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

[Solution]

1
2
3
4
5
6
7
Tree Traversal
Traverse(root, s):
    s += root;
    if (s.length == 3) result.add(s); s-> ""
    if (c1) traverse(root.c1)
    if (c2) traverse(root.c2)
    if (c3) traverse(root.c3)

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
import java.util.ListIterator;
class Solution {
    public List<String> letterCombinations(String digits) {
        HashMap<String, String[]> dict = new HashMap<String, String[]>();
        String[] arr = digits.split("");
        ArrayList<String> result = new ArrayList<String>();
        int n = digits.length();
        if (n == 0) return result;
        String[] a2 = {"a","b","c"};
        String[] a3 = {"d","e","f"};
        String[] a4 = {"g","h","i"};
        String[] a5 = {"j","k","l"};
        String[] a6 = {"m","n","o"};
        String[] a7 = {"p","q","r","s"};
        String[] a8 = {"t","u","v"};
        String[] a9 = {"w","x","y","z"};     
        dict.put("2", a2);
        dict.put("3", a3);
        dict.put("4", a4);
        dict.put("5", a5);
        dict.put("6", a6);
        dict.put("7", a7);
        dict.put("8", a8);
        dict.put("9", a9);
        
        backtrack("", -1, 0, n, arr, dict, result);
        return result;
    }
    
    public void backtrack(String s, int i, int j, int n, String[] arr, HashMap<String, String[]> dict, ArrayList<String> result) {
        if (i > -1) s += dict.get(arr[i])[j];
        if (i == n - 1) { // reach to the bottom of the tree
            result.add(s);
            s = "";
            return;
        }
        if (i + 1 < n) {
          for (j = 0; j < dict.get(arr[i + 1]).length; j++ ) {
            backtrack(s, i + 1, j, n, arr, dict, result);
            }  
        }
    }
}

46. Permutations

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
class Solution {
    
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        
        backtrack(res, new ArrayList<Integer>(), nums, new HashSet<Integer>());
        return res;
    }
    
    private void backtrack(List<List<Integer>> res, List<Integer> row, int[] nums, HashSet<Integer> set) {
        
        // Ending Condition
        if (row.size() == nums.length) {
            res.add(new LinkedList<Integer>(row));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (!set.contains(nums[i])) {
                    // 
                    row.add(nums[i]);
                    set.add(nums[i]);
                    backtrack(res, row, nums, set);
                    
                    // After get to the upper level of recursion
                    row.remove(row.size() - 1); // Remove the last element in the row
                    set.remove(nums[i]); // Remove current element from the set
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def permute(self, nums: List[int]) -> List[List[int]]:
    result = []
    n = len(nums)
    def helper(nums, row):
        if len(row) == n:
            result.append(row[:])
            row = []
            return
        for num in nums:
            if num not in row:
                row.append(num)
                helper(nums, row)
                row.pop()
    helper(nums, [])
    return result

Permutaions II

Leetcode: https://leetcode.com/problems/permutations-ii/

Note:
We use a counter dictionary to track unique elements and how many of them has been used. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    res = []
    count = collections.Counter(nums)
    def backtrack(row, res, count):
        if len(row) == len(nums):
            res.append(row[:])
            return
        for num in count:
            if count[num] > 0:
                count[num] -= 1
                backtrack(row + [num], res, count)
                count[num] += 1
    backtrack([], res, count)
    return res

526. Beautiful Arrangement

Leetcode: https://leetcode.com/problems/beautiful-arrangement/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def countArrangement(self, n: int) -> int:
    res = 0
    def backtrack(cur, index, visited):
        nonlocal res
        if index % cur == 0 or cur % index == 0:
            if index == n:
                res += 1
            visited.add(cur)
            for num in range(1, n + 1):
                if num not in visited:
                    backtrack(num, index + 1, visited)
            visited.remove(cur)
        return
    for num in range(1, n + 1):
        backtrack(num, 1, set())
    return res

77.Combinations

Leetcode: https://leetcode.com/problems/combinations/description/

Solution:

  1. Use first index to mark the current position, will help prevent repetitions
1
2
3
4
5
6
7
8
9
10
11
12
def combine(self, n: int, k: int) -> List[List[int]]:
    def backtrack(row, first):
        if len(row) == k:
            res.append(row[:])
        for i in range(first, n + 1):
            row.append(i)
            backtrack(row, i + 1)
            row.pop()
            
    res = []
    backtrack([], 1)
    return res

39. Combination Sum

Leetcode: https://leetcode.com/problems/combination-sum/description/

Video: https://www.youtube.com/watch?v=aBL-aNWNmB4

[Solution] Recursively solve the problem. Use a target to keep track of each layer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const combinationSum = (candidates, target) => {
    if (candidates.length === 0 || target === null) {
        return new Array();
    }
    candidates.sort();
    let result = new Array();
    backtrack(candidates, target, result, 0, new Array());
    return result;
};

const backtrack = (candidates, target, result, index, curRes) => {
    if (target === 0) {
        result.push(curRes.slice());
        return;
    } else if (target > 0) {
        for (let i = index; i < candidates.length; i++) {
            curRes.push(candidates[i]);
            backtrack(candidates, target - candidates[i], result, i, curRes); // target - candidate[i]
            curRes.pop(candidates[i]); // remove the last leaf on the branch to return back to an upper layer
        }
    }
}

40. Combination Sum II

Leetcode: https://leetcode.com/problems/combination-sum-ii/description/

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
const combinationSum2 = (candidates, target) => {
    if (candidates.length === 0 || target === 0) {
        return new Array();
    }
    candidates.sort((a, b) => a - b);
    let result = new Array();
    backtrack(candidates, target, 0, result, new Array());
    return result;
};

const backtrack = (candidates, target, index, result, curRes) => {
    if (target === 0) {
        result.push(curRes.slice());
        return;
    } else if (target > 0) {
        for (let i = index; i < candidates.length; i++) {
            if (i > index && candidates[i] === candidates[i - 1]) {
                continue; // skip current element, avoid repeating combinations due to duplicate elements
            }
            curRes.push(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, result, curRes);
            curRes.pop(); // remove the last element to return to an upper level
        } 
    }
}

Concise version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var combinationSum2 = function(candidates, target) {
    let res = [];
    candidates.sort();
    const backtrack = (tar, row, start) => {
        if (tar === 0) {
            res.push(row);
        } else if (tar > 0) {
            for (let i = start; i < candidates.length; i++ ) {
                if (i > start && candidates[i] === candidates[i - 1]) { continue; }
                backtrack(tar - candidates[i], [candidates[i], ...row], i + 1);
            }
        }
    }
    backtrack(target, [], 0);
    return res;
};

216. Combination Sum III

Leetcode: https://leetcode.com/problems/combination-sum-iii/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const combinationSum3 = (k, target) => {
    // Edge case
    if (k === 0 || target === 0) {
        return new Array();
    }
    const candidates = [1,2,3,4,5,6,7,8,9];
    let result = new Array();
    backtrack(k, 0, target, candidates, result, new Array());
    return result;
};

const backtrack = (k, index, target, candidates, result, curRes) => {
    if (k === 0 && target === 0) {
        result.push(curRes.slice());
        return;
    } else if (k > 0 && target > 0) {
        for (let i = index; i < candidates.length; i++ ) {
            curRes.push(candidates[i]);
            backtrack(k - 1, i + 1, target - candidates[i], candidates, result, curRes); // i + 1 to avoid use the same element more than once
            curRes.pop();
        }
    }
}

377. Combination Sum IV

Leetcode: https://leetcode.com/problems/combination-sum-iv/

Note: Use memoization.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var combinationSum4 = function(nums, target) {
    let dp = new Array(target + 1);
    dp[0] = 1;
    const backtrack = (tar, dp) => {
        if (dp[tar] > 0) { return dp[tar] }
        if (tar < 0) { return 0 }
        if (tar === 0) { return 1 }
        let res = 0;
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] > tar) { continue;}
            res += backtrack(tar - nums[i], dp);
        }
        dp[tar] = res;
        return res;
    }
    return backtrack(target, dp)
};

78. Subsets

Leetcode: https://leetcode.com/problems/subsets/submissions/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def subsets(self, nums: List[int]) -> List[List[int]]:
    if not nums:
        return [[]]
    res = []
    def backtrack(row, res, length, index):
        if len(row) == length:
            res.append(row[::])
        else:
            for i in range(index, len(nums)):
                row.append(nums[i])
                backtrack(row, res, length, i + 1)
                row.pop()
            
    for l in range(len(nums) + 1):
        backtrack([], res, l, 0)
    return res

90. Subsets II

Leetcode: https://leetcode.com/problems/subsets-ii/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = []
    def backtrack(cur, index, l):
        nonlocal res
        if len(cur) == l:
            res.append(cur)
            return
        for i in range(index, len(nums)):
            if i > index and nums[i] == nums[i - 1]:
                continue
            backtrack(cur + [nums[i]], i + 1, l)
    
    for l in range(len(nums) + 1):
        backtrack([], 0, l)
    return res

139. Word Break

Leetcode: https://leetcode.com/problems/word-break/

  • Backtrack, memoization, trie
  • Dynamic Programming solution see DP chapter
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
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    trie = {}
    for word in wordDict:
        node = trie
        for ch in word:
            if ch not in node:
                node[ch] = {}
            node = node[ch]
        node["#"] = "#"
    node = trie
    memo = {}
    def backtrack(node, string):
        nonlocal memo
        
        if string in memo:
            return memo[string]
        
        if len(string) == 0:
            # reach to the final word
            memo[string] = True
            return True
        
        for i in range(len(string)):
            ch = string[i]
            if ch in node:
                node = node[ch]
            else:
                memo[string] = False
                return False
            
            if "#" in node and backtrack(trie, string[i + 1: ]):
                # potential last character
                memo[string] = True
                return True
        memo[string] = False
        return False
    
    return backtrack(trie, s)

140. Word Break II

Leetcode: https://leetcode.com/problems/word-break-ii/

Backtracking solution (Time limit exceeds):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var wordBreak = function(s, wordDict) {
    let set = new Set([...wordDict]);
    let res = [];
    
    const backtrack = (leftString, cur) => {
        if (set.has(leftString)) {
            res.push(cur + ` ${leftString}`);
        }
        for (let i = 0; i < leftString.length; i++) {
            let sub = leftString.substring(0, i);
            if (set.has(sub)) {
                backtrack(leftString.substring(i, leftString.length), cur + ` ${sub}`);
            }
        }
    }
    backtrack(s, "");
    return res;
};

To improve the time complexity, we can try to:

  1. use a dictionary to memoize the 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def wordBreak(self, s, wordDict):
    memo = {len(s): ['']} 
    def sentences(i):
    # return all the strings s[i:] as prefix
        if i not in memo:
            temp = []
            for j in range(i + 1, len(s) + 1):
                if s[i:j] in wordDict:
                    for tail in sentences(j):
                        temp.append(s[i:j] + (tail and ' ' + tail))
            memo[i] = temp
        return memo[i]
    print(memo)
    return sentences(0)

131. Palindrome Partitioning

Leetcode: https://leetcode.com/problems/palindrome-partitioning/

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
var partition = function(s) {
    if (s.length === 0) {
        return [[]];
    }
    let res = [];
    const isPalindrome = (input, start, end) => {
        ch = input.substring(start, end + 1);
        for (let i = 0; i < ch.length / 2 + 1; i ++ ) {
            if (ch[i] !== ch[ch.length - i - 1]) {
                return false;
            }
        }
        return true
    }
    
    const backtrack = (index, row) => {
        if (row.length > 0 && index >= s.length) {
            res.push([...row]);
        } 
        for (let i = index; i < s.length; i++) {
            if (isPalindrome(s, index, i)) {
                if (index === i) {
                    backtrack(i + 1, [...row, s[i]]);
                } else {
                    backtrack(i + 1, [...row, s.substring(index, i + 1)]);
                }
            } 
        }
        
    }
    backtrack(0, [], 0);
    return res;
};

698. Partition to K Equal Sum Subsets

Leetcode: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

Video: https://www.youtube.com/watch?v=qpgqhp_9d1s&t=311s

Starting from filling 1 bucket, then 2, then 3… If there’s only one bucket unfilled left, then return true.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var canPartitionKSubsets = function(nums, k) {
    let sum = nums.reduce((val, acc) => val + acc);
    if (k === 0 || sum % k !== 0) { return false }
    let visited = new Set();
    
    const canPart = (index, curSum, tarSum, visited, k) => {
        if (curSum > tarSum) { return false }
        if (k === 0) { return true }
        if (curSum === tarSum) {
            return canPart(0, 0, tarSum, visited, k - 1);
        }
        
        for (let i = index; i < nums.length; i++) {
            if (!visited.has(i)) {
                visited.add(i);
                if (canPart(i + 1, curSum + nums[i], tarSum, visited, k)) { return true }
                visited.delete(i);
            }
        }
        return false;
    }
    return canPart(0, 0, sum / k, visited, k);
};

51. N-Queens

Leetcode: https://leetcode.com/problems/n-queens/

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
def solveNQueens(self, n: int) -> List[List[str]]:
    res = []
    queens = set()
    curComb = ["." * n] * n
    used_cols, used_rows = [0] * n, [0] * n
    used_diag, used_udiag = [0] * (2 * n - 1), [0] * (2 * n - 1)
    
    def add_solution():
        solution = []
        for _, col in sorted(queens):
            solution.append("." * col + "Q" + "." * (n - col - 1))
        res.append(solution)
        
    def visit(i, j):
        queens.add((i, j))
        used_cols[j] = 1
        used_diag[i - j] = 1# a - b
        used_udiag[i + j] = 1 # a + b

    def unvisit(i, j):
        queens.remove((i, j))
        used_cols[j] = 0
        used_diag[i - j] = 0 # a - b
        used_udiag[i + j] = 0 # a + b

    def backtrack(i = 0):
        for j in range(n):
            if used_cols[j] + used_diag[i - j] + used_udiag[i + j] == 0:
                visit(i, j)
                if i + 1 == n:
                    add_solution()
                else:
                    backtrack(i + 1)
                unvisit(i, j)
    backtrack()
    return res

489. Robot Room Cleaner

Leetcode: https://leetcode.com/problems/robot-room-cleaner/

Spiral Backtracking: Move the robot in a spiral way, if robot is surrounded by walls and visited nodes, backtrack to the previous alternative route.

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
def cleanRoom(self, robot):
        """
        :type robot: Robot
        :rtype: None
        """
        def goback():
            robot.turnRight()
            robot.turnRight()
            robot.move()
            robot.turnRight()
            robot.turnRight()
            
        def backtrack(visited, d, cell = (0, 0)):
            visited.add(cell) # add no matter wall or path
            robot.clean()
            # spiral
            for i in range(4):
                new_dir = (d + i) % 4
                new_cell = (cell[0] + new_dir, cell[1] + new_dir)
                
                if new_cell not in visited and robot.move():
                    backtrack(new_cell, visited, new_dir)
                    goback() # backtrack
                robot.turnRight()
                
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        backtrack(set(), 0)

282. Expression Add Operators

Leetcode: https://leetcode.com/problems/expression-add-operators/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def addOperators(self, num, target):
    res = []
    def backtrack(curSum, index, row, res, curNum, prevNum):
        if index == len(num):
            if curSum == target and curNum == 0: # !! if no number is left unprocessed
                res.append(row[1:])
            return
        
        curNum = curNum * 10 + int(num[index])
        
        if curNum > 0: # !! Avoid invalid number like 05
            backtrack(curSum, index + 1, row, res, curNum, prevNum)
            
        # +
        backtrack(curSum + curNum, index + 1, row + "+" + str(curNum), res, 0, curNum)
        
        # -
        if row:
            backtrack(curSum - curNum, index + 1, row + "-" + str(curNum), res, 0, -curNum)
            
        # * 
            backtrack(curSum - prevNum + (curNum * prevNum), index + 1, row + "*" + str(curNum), res, 0, curNum * prevNum)
    backtrack(0, 0, "", res, 0, 0)
    return res

93. Restore IP Addresses

Leetcode: https://leetcode.com/problems/restore-ip-addresses/

Note:

  • A lot of edge cases to consider
  • In each recursion layer, we add first three digits to the current number
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def restoreIpAddresses(self, s):
    res = []
    def backtrack(leftS, row, curNum, res):
        if curNum == leftS == "" and len(row) < 4:
            return
        if curNum and curNum[0] == '0' and len(curNum) != 1:
            return
        if curNum and int(curNum) > 255 or len(row) > 4:
            return
        if len(row) == 4 and leftS == "" and curNum == "":
            res.append('.'.join(row))
            return
        if curNum:
            row.append(str(curNum))
        for i in range(3):
            backtrack(leftS[i + 1:], row, leftS[: i + 1], res)
        if curNum:
            row.pop()
        
    for i in range(3):
        backtrack(s[i + 1:], [], s[: i + 1], res)
    return list(set(res))