# DFS + Backtracking

### When to use Backtracking

* Basically, going back to the previous level and check the unvisited neighboring nodes.  顾名思义，回溯。即**回到上一层**查未**查过的**邻节点。
* Brute force solution, usually to list all the possibilities. **暴力解法，穷举所有可能性**

### Notes 注意一些坑

* 对于全局变量，如visited\[]\[]，需在**访问下一层之前置true**，并在**返回上一层之前置false**
* what to return when meet the termination conditions，如**越界**，**无限循环（访问已访问过的节点）**，**触底**等

## 经典题目

[_17 Letter Combinations of a Phone Number_ ](https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/)\
[_39 Combination Sum_](https://leetcode.com/problems/combination-sum/description/)\
[_351 Android Unlock Patterns_](https://leetcode.com/problems/android-unlock-patterns/description/)

{% tabs %}
{% tab title="17" %}
```java
String[] dict = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
    List<String> res = new ArrayList<>();
    if (digits == null || digits.length() == 0) return res;
    StringBuilder cur = new StringBuilder();
    helper(digits, 0, cur, res);
    return res;
}
private void helper(String digits, int index, StringBuilder sb, List<String> res) {
    // base case
    if (index == digits.length()) {
        res.add(sb.toString());
        return;
    }
    String chars = dict[digits.charAt(index) - '0'];
    for (int i = 0; i < chars.length(); i++) {
        sb.append(chars.charAt(i));
        helper(digits, index + 1, sb, res);
        sb.deleteCharAt(sb.length() - 1);
    }
}
```
{% endtab %}

{% tab title="39" %}
```java
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if (candidates == null || candidates.length == 0) return res;
    Arrays.sort(candidates);
    List<Integer> cur = new ArrayList<>();
    helper(candidates, 0, target, cur, res);
    return res;
}
private void helper(int[] candidates, int index, int target, List<Integer> cur, List<List<Integer>> res) {
    if (target == 0) {
        res.add(new ArrayList<Integer>(cur));
        return;
    }
    for (int i = index; i < candidates.length; i++) {
        if (target >= candidates[i]) {
            cur.add(candidates[i]);
            helper(candidates, i, target - candidates[i], cur, res);
            cur.remove(cur.size() - 1);
        }
    }
}
```
{% endtab %}

{% tab title="351" %}
```java
// Method 1
class Solution {
    private int[][] dir1s = {{0,-1},{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1,1}, {1, 0}, {1,-1}};
    private int[][] dir2s = {{0,-2},{-1,-2},{-2,-2},{-2,-1},{-2,0},{-2,1},{-2,2},{-1,2},{0,2},{1,2},{2,2},{2,1},{2,0},{2,-1},{2,-2}, {1,-2}};
    
    public int numberOfPatterns(int m, int n) {
        int ans = 0;
        for (int i = m; i <= n; i++) {
            boolean[][] visited = new boolean[3][3];
            ans += 4 * helper(i - 1, 0, 1, visited);
            ans += 4 * helper(i - 1, 0, 0, visited);
            ans += helper(i - 1, 1, 1, visited);
        }
        return ans;
    }
    
    private int helper(int count, int row, int col, boolean[][] visited) {
        if (row < 0 || row >= visited.length || col < 0 || col >= visited[0].length || visited[row][col]) {
            return 0;
        }
        if (count == 0) {
            return 1;
        }
        visited[row][col] = true;
        int ans = 0;
        for (int i = 0; i < dir1s.length; i++) {
            int x = row + dir1s[i][0];
            int y = col + dir1s[i][1];
            ans += helper(count - 1, x, y, visited);
        }
        for (int i = 0; i < dir2s.length; i++) {
            int x = row + dir2s[i][0];
            int y = col + dir2s[i][1];
            if (row == x && !visited[row][1]) {
                continue;
            } else if (col == y && !visited[1][col]) {
                continue;
            }
            if (x + row == 2 && y + col == 2 && !visited[1][1]) {
                continue;
            }
            ans += helper(count - 1, x, y, visited);
        }
        visited[row][col] = false;
        return ans;
    }
}
/*
 *    Method 2
 *    Optimized validity checking with the help of skip matrix
        int[][] skip = new int[10][10];
        skip[1][3] = skip[3][1] = 2;
        skip[3][9] = skip[9][3] = 6;
        skip[7][9] = skip[9][7] = 8;
        skip[1][7] = skip[7][1] = 4;
        skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[6][4] = skip[4][6] = 5;
        
*/
```
{% endtab %}
{% endtabs %}



[_247 Strobogrammatic Number II_](https://leetcode.com/problems/strobogrammatic-number-ii/description/)\
[_248 Strobogrammatic Number III_](https://leetcode.com/problems/strobogrammatic-number-iii/description/)

{% tabs %}
{% tab title="247" %}
```java
class Solution {
    private char[][] pairs = {{'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}};
    public List<String> findStrobogrammatic(int n) {
        List<String> ans = new ArrayList<>();
        if (n == 0) return ans;
        char[] array = new char[n];
        helper((n - 1) / 2, n / 2, array, ans);
        return ans;
    }
    private void helper(int left, int right, char[] array, List<String> ans) {
        if (left < 0) {
            ans.add(new String(array));
            return;
        }
        if (left == right) {
            for (int i = 0; i < 3; i++) {
                char tmpLeft = array[left];
                array[left] = pairs[i][0];
                helper(left - 1, right + 1, array, ans);
                array[left] = tmpLeft;
            }
        } else if (left > 0) {
            for (int i = 0; i < pairs.length; i++) {
                char tmpLeft = array[left];
                char tmpRight = array[right];
                array[left] = pairs[i][0];
                array[right] = pairs[i][1];
                helper(left - 1, right + 1, array, ans);
                array[left] = tmpLeft;
                array[right] = tmpRight;
            }
        } else if (left == 0) {
            for (int i = 1; i < pairs.length; i++) {
                char tmpLeft = array[left];
                char tmpRight = array[right];
                array[left] = pairs[i][0];
                array[right] = pairs[i][1];
                helper(left - 1, right + 1, array, ans);
                array[left] = tmpLeft;
                array[right] = tmpRight;
            }
        }
    }
}
```
{% endtab %}

{% tab title="248" %}
```java
// 按长度，穷举所有可能性
// 注意终止条件（长度相等且在范围内），以及 如何判断number是否有效

class Solution {
    private char[][] pairs = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
    public int strobogrammaticInRange(String low, String high) {
        int[] ans = new int[] { 0 };
        for (int length = low.length(); length <= high.length(); length++) {
            char[] array = new char[length];
            helper(0, length - 1, array, low, high, ans);
        }
        return ans[0];
    }
    
    // Return the number of valid stro numbers of certain length
    private void helper(int left, int right, char[] array, String low, String high, int[] ans) {
        if (left > right) {
            String cur = new String(array);
            if ((cur.length() == low.length() && cur.compareTo(low) < 0) || 
                (cur.length() == high.length() && cur.compareTo(high) > 0)) {
                return;
            }
            ans[0]++;
            return;
        }
        
        for (char[] pair: pairs) {
            array[left] = pair[0];
            array[right] = pair[1];
            if (array.length != 1 && array[0] == '0') {
                continue;
            }
            if (left == right && pair[0] != pair[1]) {
                continue;
            }
            helper(left + 1, right - 1, array, low, high, ans);
        }
    }
}
```
{% endtab %}
{% endtabs %}



[_301 Remove Invalid Parentheses_](https://leetcode.com/problems/remove-invalid-parentheses/description/)

{% tabs %}
{% tab title="301 DFS" %}
```java
// 首先，扫一遍string，得到需要删除的 ( 和 ) 数量。
// 再用 DFS 寻找满足条件，即有效的，并且唯一的，substring。
// 这里关键的点在于剪枝，如果在寻找的过程中需要删除的 '(' 小于 0 或
//        需要删除的 ')' 小于0 或
//        当前构成的substring invalid，则直接返回。

public List<String> removeInvalidParentheses(String s) {
        int leftToRemove = 0, rightToRemove = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                leftToRemove += 1;
            } else if (s.charAt(i) == ')') {
                if (leftToRemove == 0) {
                    rightToRemove += 1;
                } else {
                    leftToRemove -= 1;
                }
            }
        }
        Set<String> ans = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        dfs(s, 0, leftToRemove, rightToRemove, 0, sb, ans);
        return new ArrayList<String>(ans);
    }
    
    private void dfs(String s, int curIndex, int leftToRemove, int rightToRemove, int valid, StringBuilder sb, Set<String> ans) {
        if (leftToRemove < 0 || rightToRemove < 0 || valid < 0) {
            return;
        }
        if (curIndex == s.length()) {
            if (leftToRemove == 0 && rightToRemove == 0 && valid == 0) {
                ans.add(sb.toString());
            }
            return;
        }
        char c = s.charAt(curIndex);
        int length = sb.length();
        if (c == '(') {
            dfs(s, curIndex + 1, leftToRemove - 1, rightToRemove, valid, sb, ans);  // not use '('
            dfs(s, curIndex + 1, leftToRemove, rightToRemove, valid + 1, sb.append(c), ans); // use '('
        } else if (c == ')') {
            dfs(s, curIndex + 1, leftToRemove, rightToRemove - 1, valid, sb, ans);  // not use ')'
            dfs(s, curIndex + 1, leftToRemove, rightToRemove, valid - 1, sb.append(c), ans); // use ')'
        } else {
            dfs(s, curIndex + 1, leftToRemove, rightToRemove, valid, sb.append(c), ans); // use letters
        }
        sb.setLength(length);
    }
```
{% endtab %}

{% tab title="301 BFS" %}
```java
// 思路很巧妙，利用 BFS 找最短路径的思想，从input string出发，以删除的个数为depth。
// 对于每层不同的 node，将所有删除一个'('或')'的子字符串作为child node存进queue。
// 直到找到 valid 的 node，就无需再往下走，因为已经不是minimum deletion了。

public List<String> removeInvalidParentheses(String s) {
    List<String> ans = new ArrayList<>();
    Set<String> visited = new HashSet<>();
    Deque<String> queue = new LinkedList<>();
    queue.add(s);
    visited.add(s);
    while (!queue.isEmpty()) {
        int size = queue.size();
        int ansSize = ans.size();
        while (size-- > 0) {
            String cur = queue.pollFirst();
            if (isValid(cur)) {
                ans.add(cur);
            } else {
                for (int i = 0; i < cur.length(); i++) {
                    if (cur.charAt(i) == '(' || cur.charAt(i) == ')') {
                        String next = cur.substring(0, i) + cur.substring(i + 1);
                        if (!visited.contains(next)) {
                            queue.add(next);
                            visited.add(next);
                        }
                    }   
                }
            }
        }
        if (ans.size() > ansSize) {
            break;
        }
    }
    return ans;
}

private boolean isValid(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') count++;
        if (s.charAt(i) == ')') count--;
        if (count < 0) return false;
    }
    return count == 0;
}
```
{% endtab %}
{% endtabs %}

