Leetcode回溯

17. 电话号码的字母组合

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder temp = new StringBuilder();
    String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    void dfs(int index, String digits) {
        if (index == digits.length()) {
            res.add(temp.toString());
            return;
        }
        int num = digits.charAt(index) - '0';
        for (int i = 0; i < map[num].length(); i++) {
            temp.append(map[num].charAt(i));
            dfs(index + 1, digits);
            temp.deleteCharAt(temp.length() - 1);
        }
    }

    public List<String> letterCombinations(String digits) {
        if ("".equals(digits)) {
            return new ArrayList<>();
        }
        dfs(0, digits);
        return res;
    }
}

22. 括号生成

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder temp = new StringBuilder();

    void dfs(int index, int left, int right, int n) {
        //剪枝
        if (left == n + 1 || right > left) {
            return;
        }
        if (index == 2 * n) {
            res.add(temp.toString());
            return;
        }
        temp.append("(");
        dfs(index + 1, left + 1, right, n);
        temp.deleteCharAt(temp.length() - 1);
        temp.append(")");
        dfs(index + 1, left, right + 1, n);
        temp.deleteCharAt(temp.length() - 1);
    }

    public List<String> generateParenthesis(int n) {
        dfs(0, 0, 0, n);
        return res;
    }
}

37. 解数独

class Solution {
    public boolean dfs(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(i, j, c, board) == true) {
                            board[i][j] = c;
                            if (dfs(board) == true) {
                                return true;
                            } else {
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    boolean isValid(int row, int col, char c, char[][] board) {
        int blockRow = 3 * (row / 3);
        int blockCol = 3 * (col / 3);
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == c) {
                return false;
            }
            if (board[row][i] == c) {
                return false;
            }
            if (board[blockRow + i / 3][blockCol + i % 3] == c) {
                return false;
            }
        }
        return true;
    }

    public void solveSudoku(char[][] board) {
        dfs(board);
    }
}

39. 组合总和

组合问题，使用index防止重复。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    void dfs(int index, int sum, int target, int[] candidates) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            res.add(new ArrayList<>(temp));
        }
        for (int i = index; i < candidates.length; i++) {
            temp.add(candidates[i]);
            dfs(i, sum + candidates[i], target, candidates);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(0, 0, target, candidates);
        return res;
    }
}

40. 组合总和 II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    void dfs(int index, int sum, int target, int[] candidates) {
        if (index > candidates.length || sum > target) {
            return;
        }
        if (sum == target) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            if (i - 1 >= index && candidates[i] == candidates[i - 1]) {
                continue;
            }
            temp.add(candidates[i]);
            dfs(i + 1, sum + candidates[i], target, candidates);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(0, 0, target, candidates);
        return res;
    }
}

46. 全排列

排列问题使用isVisit数组标记某个元素是否已访问。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    boolean[] isVisit;

    void dfs(int index, int[] nums) {
        if (index == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (isVisit[i] == false) {
                isVisit[i] = true;
                temp.add(nums[i]);
                dfs(index + 1, nums);
                temp.remove(temp.size() - 1);
                isVisit[i] = false;
            }
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        isVisit = new boolean[nums.length];
        dfs(0, nums);
        return res;
    }
}

47. 全排列 II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    boolean[] isVisit;

    void dfs(int[] nums) {
        if (temp.size() == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //isVisit[i - 1] == false时说明到达同一层相同的地方
            if (i - 1 >= 0 && nums[i] == nums[i - 1] && isVisit[i - 1] == false) {
                continue;
            }
            if (isVisit[i] == false) {
                isVisit[i] = true;
                temp.add(nums[i]);
                dfs(nums);
                temp.remove(temp.size() - 1);
                isVisit[i] = false;
            }
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        isVisit = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums);
        return res;
    }
}

51. N 皇后

class Solution {
    List<List<String>> res = new ArrayList<>();
    boolean[] isVisit;
    int[] arr;

    boolean judge(int n) {
        boolean flag = true;
        boolean flag2 = true;//使用标记快速跳出双重for循环
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (Math.abs(i - j) == Math.abs(arr[i] - arr[j])) {//在对角线上
                    flag = false;
                    flag2 = false;
                    break;
                }
            }
            if (flag2 == false) {
                break;
            }
        }
        return flag;
    }

    void dfs(int index, int n) {
        if (index == n + 1) {
            if (judge(n) == true) {
                List<String> list = new ArrayList<>();
                for (int i = 1; i <= n; i++) {
                    int col = arr[i];
                    StringBuilder sb = new StringBuilder();
                    for (int j = 1; j <= n; j++) {
                        if (j != col) {
                            sb.append(".");
                        } else {
                            sb.append("Q");
                        }
                    }
                    list.add(sb.toString());
                }
                res.add(list);
            }
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (isVisit[i] == false) {
                arr[index] = i;
                isVisit[i] = true;
                dfs(index + 1, n);
                isVisit[i] = false;
            }
        }
    }

    public List<List<String>> solveNQueens(int n) {
        isVisit = new boolean[n + 1];
        arr = new int[n + 1];
        dfs(1, n);
        return res;
    }
}

52. N皇后 II

class Solution {
    int res = 0;
    boolean[] isVisit;
    int[] arr;

    boolean judge(int n) {
        boolean flag = true;
        boolean flag2 = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (Math.abs(i - j) == Math.abs(arr[i] - arr[j])) {//在对角线上
                    flag = false;
                    flag2 = false;
                    break;
                }
            }
            if (flag2 == false) {
                break;
            }
        }
        return flag;
    }

    void dfs(int index, int n) {
        if (index == n + 1) {
            if (judge(n) == true) {
                res++;
            }
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (isVisit[i] == false) {
                arr[index] = i;
                isVisit[i] = true;
                dfs(index + 1, n);
                isVisit[i] = false;
            }
        }
    }

    public int totalNQueens(int n) {
        isVisit = new boolean[n + 1];
        arr = new int[n + 1];
        dfs(1, n);
        return res;
    }
}

60. 第k个排列

class Solution {
    boolean[] isVisit;
    StringBuilder res;
    StringBuilder temp = new StringBuilder();
    int count = 0;

    void dfs(int index, int n, int k) {

        if (index == n + 1) {
            count++;
            if (count == k) {
                res = new StringBuilder(temp);
            }
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (isVisit[i] == false) {
                temp.append(i);
                isVisit[i] = true;
                dfs(index + 1, n, k);
                isVisit[i] = false;
                temp.deleteCharAt(temp.length() - 1);
            }
        }
    }

    public String getPermutation(int n, int k) {
        isVisit = new boolean[n + 1];
        dfs(1, n, k);
        return res.toString();
    }
}

77. 组合

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    void dfs(int index, int n, int k) {
        if (temp.size() == k) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i <= n; i++) {
            temp.add(i);
            dfs(i + 1, n, k);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        dfs(1, n, k);
        return res;
    }
}

78. 子集

可以使用选与不选的dfs。
也可以使用在递归的过程中就把temp加入到res中。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    void dfs(int index, int[] nums) {
        if (index == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }
        temp.add(nums[index]);
        dfs(index + 1, nums);
        temp.remove(temp.size() - 1);
        dfs(index + 1, nums);
    }

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums);
        return res;
    }
}

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    void dfs(int index, int[] nums) {
        if (index == nums.length) {
            return;
        }
        for (int i = index; i < nums.length; i++) {
            temp.add(nums[i]);
            res.add(new ArrayList<>(temp));
            dfs(i + 1, nums);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums);
        res.add(new ArrayList<>());
        return res;
    }
}

79. 单词搜索

class Solution {

    boolean[][] isVisit;
    int[] X = {0, 0, -1, 1};//上下左右
    int[] Y = {-1, 1, 0, 0};

    //对所有规则进行判断
    boolean check(char[][] board, int i, int j, int k, String word) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return false;
        }
        if (isVisit[i][j] == true) {
            return false;
        }
        if (board[i][j] == word.charAt(k)) {
            return true;
        } else {
            return false;
        }
    }


    boolean dfs(char[][] board, int i, int j, int k, String word) {
        if (k == word.length()) {
            return true;
        }
        if (check(board, i, j, k, word) == true) {
            isVisit[i][j] = true;
            for (int z = 0; z < 4; z++) {
                int newI = i + X[z];
                int newJ = j + Y[z];
                if (dfs(board, newI, newJ, k + 1, word) == true) {
                    return true;
                }
            }
            //如果某一点四个方向都不满足条件，改回false
            isVisit[i][j] = false;
        } else {
            return false;
        }
        return false;
    }

    public boolean exist(char[][] board, String word) {
        isVisit = new boolean[board.length][board[0].length];
        //从每一个字母开始出发进行DFS
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                boolean res = dfs(board, i, j, 0, word);
                if (res == true) {
                    return true;
                } else {
                    continue;
                }
            }
        }
        return false;
    }
}

89. 格雷编码

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        int head = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = res.size() - 1; j >= 0; j--) {
                res.add(res.get(j) + head);
            }
            head <<= 1;
        }
        return res;
    }
}

90. 子集 II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    void dfs(int index, int[] nums) {
        if (index == nums.length) {
            return;
        }
        for (int i = index; i < nums.length; i++) {
            if (i - 1 >= index && nums[i] == nums[i - 1]) {
                continue;
            }
            temp.add(nums[i]);
            res.add(new ArrayList<>(temp));
            dfs(i + 1, nums);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        res.add(new ArrayList<>());
        dfs(0, nums);
        return res;
    }
}

93. 复原IP地址

class Solution {
    List<String> res = new ArrayList<>();
    List<String> segment = new ArrayList<>();

    void dfs(int index, String s) {
        if (index == s.length() && segment.size() == 4) {
            StringBuilder t = new StringBuilder();
            for (String se : segment) t.append(se).append(".");
            t.deleteCharAt(t.length() - 1);
            res.add(t.toString());
            return;
        }
        if (index < s.length() && segment.size() == 4) {
            return;
        }

        for (int i = 1; i <= 3; i++) {
            if (index + i > s.length()) {
                return;
            }
            if (i != 1 && s.charAt(index) == '0') {
                return;
            }
            String str = s.substring(index, index + i);
            if (i == 3 && Integer.parseInt(str) > 255) {
                return;
            }
            segment.add(str);
            dfs(index + i, s);
            segment.remove(segment.size() - 1);
        }
    }

    public List<String> restoreIpAddresses(String s) {
        dfs(0, s);
        return res;
    }
}

131. 分割回文串

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> temp = new ArrayList<>();

    boolean isPalindromic(String s) {
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }

    void dfs(int index, String s) {
        if (index == s.length()) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            String str = s.substring(index, i + 1);
            if (isPalindromic(str) == true) {
                temp.add(str);
                dfs(i + 1, s);
                temp.remove(temp.size() - 1);
            }
        }
    }

    public List<List<String>> partition(String s) {
        dfs(0, s);
        return res;
    }
}

132. 分割回文串 II

超时了，思路是正确的。
待优化成动态规划做。

class Solution {
    int res = Integer.MAX_VALUE;
    List<String> temp = new ArrayList<>();

    public boolean isPar(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

    public void dfs(int begin, String s) {
        if (begin == s.length()) {
            res = Math.min(res, temp.size() - 1);
        }
        for (int i = begin; i < s.length(); i++) {
            String sub = s.substring(begin, i + 1);
            if (isPar(sub) == true) {
                temp.add(sub);
                dfs(i + 1, s);
                temp.remove(temp.size() - 1);
            }
        }
    }

    public int minCut(String s) {
        dfs(0, s);
        return res;
    }
}