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 39 Combination Sum 351 Android Unlock Patterns

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);
    }
}

247 Strobogrammatic Number II 248 Strobogrammatic Number III

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;
            }
        }
    }
}

301 Remove Invalid Parentheses

// 首先，扫一遍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);
    }

PreviousDFSNextAdvanced Algorithm

Last updated