Skip to content

Latest commit

 

History

History
1331 lines (1165 loc) · 39.1 KB

回溯算法.md

File metadata and controls

1331 lines (1165 loc) · 39.1 KB

[TOC]

17. 电话号码的字母组合

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例:

输入:"23" 输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 说明: 尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。

回溯算法

class Solution {
    Map<String, String> map = new HashMap<String, String>() {{
        put("2", "abc");
        put("3", "def");
        put("4", "ghi");
        put("5", "jkl");
        put("6", "mno");
        put("7", "pqrs");
        put("8", "tuv");
        put("9", "wxyz");
    }};
    List<String> out = new ArrayList<String>();
    private void backtrack(String combination, String digits){
        if (digits.length() == 0){
            out.add(combination);
        } else {
            String digit = digits.substring(0, 1);
            String letters = map.get(digit);
            for (int i = 0; i < letters.length(); ++i){
                String letter = letters.substring(i, i + 1);
                backtrack(combination + letter, digits.substring(1));
            }
        }
    }
    public List<String> letterCombinations(String digits) {
        if (digits.length() != 0){
            backtrack("", digits);
        }
        return out;
    }
}

93. 复原IP地址

93. 复原IP地址

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"]

回溯

class Solution {
    int n;
    String s;
    List<String> res = new ArrayList<>();
    Deque<String> segments = new LinkedList<>();
    private boolean valid(String segment) {
        int m = segment.length();
        if (m > 3) {
            return false;
        }
        return (segment.charAt(0) != '0') ? (Integer.valueOf(segment) <= 255) : m == 1;
    }
    private void updateOutput(int curPos) {
        String segment = s.substring(curPos + 1, n);
        if (valid(segment)) {
            segments.add(segment);
            res.add(String.join(".", segments));
            segments.removeLast();
        }
    }
    private void backtrace(int prev, int dots) {
        int maxPos = Math.min(prev + 4, n - 1);
        for (int cur = prev + 1; cur < maxPos; cur++) {
            String segment = s.substring(prev + 1, cur + 1);
            if (valid(segment)) {
                segments.add(segment);
                if (dots == 1) {
                    updateOutput(cur);
                } else {
                    backtrace(cur, dots - 1);
                }
                segments.removeLast();
            }
        }
    }
    public List<String> restoreIpAddresses(String s) {
        n = s.length();
        this.s = s;
        backtrace(-1, 3);
        return res;
    }
}

79. 单词搜索

79. 单词搜索

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ]

给定 word = "ABCCED", 返回 true. 给定 word = "SEE", 返回 true. 给定 word = "ABCB", 返回 false.

回溯算法

class Solution {
    private int m, n;
    int[][] directions = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    public boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0) {
            return true;
        }
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        m = board.length;
        n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(0, i, j, visited, board, word)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(int curLen, int row, int col, boolean[][] visited, char[][] board, String word) {
        if (curLen == word.length()) {
            return true;
        }
        if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != word.charAt(curLen) || visited[row][col]) {
            return false;
        }
        visited[row][col] = true;
        for (int[] d : directions) {
            if (dfs(curLen + 1, row + d[0], col + d[1], visited, board, word)) {
                return true;
            }
        }
        visited[row][col] = false;
        return false;
    }
}

257. 二叉树的所有路径

257. 二叉树的所有路径

给定一个二叉树,返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

1 /
2 3
5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

回溯

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private void backtrace(TreeNode node, List<String> res, List<Integer> values) {
        if (node == null) {
            return;
        }
        values.add(node.val);
        if (isLeaf(node)) {
            res.add(buildPath(values));
        } else {
            backtrace(node.left, res, values);
            backtrace(node.right, res, values);
        }
        values.remove(values.size() - 1);
    }
    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }
    private String buildPath(List<Integer> values) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.size(); i++) {
            sb.append(values.get(i));
            if (i != values.size() - 1) {
                sb.append("->");
            }
        }
        return sb.toString();
    }
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        List<Integer> values = new ArrayList<>();
        backtrace(root, res, values);
        return res;
    }
}

46. 全排列

46. 全排列

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

回溯算法

class Solution {
    private void backtrack(List<Integer> permute, List<List<Integer>> permutes, boolean[] visited, int[] nums) {
        if (permute.size() == nums.length) {
            permutes.add(new ArrayList<>(permute));
            return;
        }
        for (int i = 0; i < visited.length; ++i) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            permute.add(nums[i]);
            backtrack(permute, permutes, visited, nums);
            permute.remove(permute.size() - 1);
            visited[i] = false;
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> permutes = new ArrayList<>();
        List<Integer> permute = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        backtrack(permute, permutes, visited, nums);
        return permutes;
    }
}

47. 全排列 II

47. 全排列 II

给定一个可包含重复数字的序列,返回所有不重复的全排列。

示例:

输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]

回溯算法

在实现上,和 Permutations 不同的是要先排序,然后在添加一个元素时,判断这个元素是否等于前一个元素,如果等于,并且前一个元素还未访问,那么就跳过这个元素。

class Solution {
    private void backtrack(List<List<Integer>> permutes, List<Integer> permute, boolean[] visited, int[] nums) {
        if (permute.size() == nums.length) {
            permutes.add(new ArrayList<>(permute));
            return;
        }
        for (int i = 0; i < nums.length; ++i){
            if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue;
            }
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            permute.add(nums[i]);
            backtrack(permutes, permute, visited, nums);
            permute.remove(permute.size() - 1);
            visited[i] = false;
        }
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> permutes = new ArrayList<>();
        List<Integer> permute = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        backtrack(permutes, permute, visited, nums);
        return permutes;
    }
}

剑指 Offer 38. 字符串的排列

剑指 Offer 38. 字符串的排列

输入一个字符串,打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

示例:

输入:s = "abc"
输出:["abc","acb","bac","bca","cab","cba"]
 

限制:

1 <= s 的长度 <= 8

回溯

详解见https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/

class Solution {
    List<String> res = new LinkedList<>();
    char[] c;
    private void dfs(int x) {
        if (x == c.length -1) {
            res.add(String.valueOf(c));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = x; i < c.length; i++) {
            if (set.contains(c[i])) {
                continue;
            }
            set.add(c[i]);
            swap(i, x);
            dfs(x + 1);
            swap(i, x);
        }
    }
    private void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
}

77. 组合

77. 组合

给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

回溯算法

按照上面的套路,不过不是最优的方法。

class Solution {
    private void backtrack(List<List<Integer>> combinations, List<Integer> combination, int n, int k, boolean[] visited) {
        if (combination.size() == k) {
            combinations.add(new ArrayList<>(combination));
            return;
        }
        for (int i = 1; i <= n; ++i) {
            if (visited[i]) {
                return;
            }
            visited[i] = true;
            combination.add(i);
            backtrack(combinations, combination, n, k, visited);
            combination.remove(combination.size() - 1);
            visited[i] = false;
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> combinations  = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        boolean[] visited = new boolean[n + 1];
        backtrack(combinations, combination, n, k, visited);
        return combinations;
    }
}

回溯

稍微优化一下

class Solution {
    private void backtrace(List<List<Integer>> combinations, List<Integer> combination, int start, int n, int k) {
        if (combination.size() == k) {
            combinations.add(new ArrayList<>(combination));
            return;
        }
        for (int i = start; i <= n; i++) {
            combination.add(i);
            backtrace(combinations, combination, i + 1, n, k);
            combination.remove(combination.size() - 1);
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> combinations = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        backtrace(combinations, combination, 1, n, k);
        return combinations;
    }
}

剪枝操作

关于剪枝操作的讲解部分见https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/

class Solution {
    private void backtrack(List<List<Integer>> combinations, List<Integer> combination, int start, int n, int k) {
        if (k == 0) {
            combinations.add(new ArrayList<>(combination));
            return;
        }
        for (int i = start; i <= n - k + 1; ++i) { // 剪枝操作
            combination.add(i);
            backtrack(combinations, combination, i + 1, n, k - 1);
            combination.remove(combination.size() - 1);
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> combinations  = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        boolean[] visited = new boolean[n + 1];
        backtrack(combinations, combination, 1, n, k);
        return combinations;
    }
}

39. 组合总和

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。 解集不能包含重复的组合。 示例 1:

输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] 示例 2:

输入: candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]

回溯算法

class Solution {
    private void backtrace(List<List<Integer>> combinations, List<Integer> combination, int start, int[] candidates, int target) {
        if (target == 0) {
            combinations.add(new ArrayList<>(combination));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            int temp = candidates[i];
            if (temp <= target) {
                combination.add(temp);
                backtrace(combinations, combination, i, candidates, target - temp);
                combination.remove(combination.size() - 1);
            }
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> combinations = new ArrayList<>();
        backtrace(combinations, new ArrayList<>(), 0, candidates, target);
        return combinations;
    }
}

40. 组合总和 II

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明:

所有数字(包括目标数)都是正整数。 解集不能包含重复的组合。 示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] 示例 2:

输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]

回溯、剪枝

class Solution {
    private void backtrace(List<List<Integer>> combinations, List<Integer> combination, int start, int[] candidates, int target, boolean[] visited) {
        if (target == 0) {
            combinations.add(new ArrayList<>(combination));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            int temp = candidates[i];
            if (i != 0 && candidates[i - 1] == candidates[i] && !visited[i - 1]) {
                continue;
            }
            if (temp <= target) {
                visited[i] = true;
                combination.add(temp);
                backtrace(combinations, combination, i + 1, candidates, target - temp, visited);
                combination.remove(combination.size() - 1);
                visited[i] = false;
            } else {
                break;
            }
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> combinations = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        Arrays.sort(candidates);
        boolean[] visited = new boolean[candidates.length];
        backtrace(combinations, combination, 0, candidates, target, visited);
        return combinations;
    }
}

回溯,不需要visited

import java.util.*;
public class Solution {
    private ArrayList<ArrayList<Integer>> res;
    private ArrayList<Integer> cur;
    private void backtrace(int[] num, int target, int start) {
        if (target == 0) {
            res.add(new ArrayList(cur));
            return;
        }
        for (int i = start; i < num.length; i++) {
            int temp = num[i];
            // i > start是关键
            if (i > start && num[i - 1] == num[i] ) {
                continue;
            }
            if (temp <= target) {
                cur.add(temp);
                backtrace(num, target - temp, i + 1);
                cur.remove(cur.size() - 1);
            } else {
                break;
            }
        }
    }
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        res = new ArrayList();
        cur = new ArrayList();
        Arrays.sort(num);
        backtrace(num, target, 0);
        return res;
    }
}

216. 组合总和 III

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

说明:

所有数字都是正整数。 解集不能包含重复的组合。 示例 1:

输入: k = 3, n = 7 输出: [[1,2,4]] 示例 2:

输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

回溯算法

class Solution {
    int num;
    private void backtrace(List<List<Integer>> combinations, List<Integer> combination, int start, int k, int n) {
        if (n == 0 && combination.size() == num) {
            combinations.add(new ArrayList<>(combination));
            return;
        }
        for (int i = start; i <= 9 - k + 1; i++) {
            if (i <= n) {
                combination.add(i);
                backtrace(combinations, combination, i + 1, k - 1, n - i);
                combination.remove(combination.size() - 1);
            } else {
                break;
            }
        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> combinations = new ArrayList<>();
        num = k;
        backtrace(combinations, new ArrayList<>(), 1, k, n);
        return combinations;
    }
}

78. 子集

78. 子集

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

回溯算法

class Solution {
    private void backtrace(List<List<Integer>> result, List<Integer> temp, int start, int[] nums, int size) {
        if (temp.size() == size) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            temp.add(nums[i]);
            backtrace(result, temp, i + 1, nums, size);
            temp.remove(temp.size() - 1);
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++) {
            backtrace(result, new ArrayList<>(), 0, nums, i);
        }
        return result;
    }
}

90. 子集 II

90. 子集 II

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

输入: [1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

回溯算法

class Solution {
    private void backtrace(List<List<Integer>> result, List<Integer> temp, int start, int[] nums, int size, boolean[] visited) {
        if (temp.size() == size) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i != 0 && nums[i - 1] == nums[i] && !visited[i - 1]) {
                continue;
            }
            visited[i] = true;
            temp.add(nums[i]);
            backtrace(result, temp, i + 1, nums, size, visited);
            visited[i] = false;
            temp.remove(temp.size() - 1);
        }
    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        for (int i = 0; i <= nums.length; i++) {
            backtrace(result, new ArrayList<>(), 0, nums, i, visited);
        }
        return result;
    }
}

剑指 Offer 12. 矩阵中的路径

剑指 Offer 12. 矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。

[["a","b","c","e"], ["s","f","c","s"], ["a","d","e","e"]]

但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。

示例 1:

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true
示例 2:

输入:board = [["a","b"],["c","d"]], word = "abcd"
输出:false
提示:

1 <= board.length <= 200
1 <= board[i].length <= 200

回溯

class Solution {
    private int m, n;
    private int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0) {
            return true;
        }
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        m = board.length;
        n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(0, i, j, visited, board, word)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(int curLen, int r, int c, boolean[][] visited, char[][] board, String word) {
        if (curLen == word.length()) {
            return true;
        }
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(curLen) || visited[r][c]) {
            return false;
        }
        visited[r][c] = true;
        for (int[] d : direction) {
            if (dfs(curLen + 1, r + d[0], c + d[1], visited, board, word)) {
                return true;
            }
        }
        visited[r][c] = false;
        return false;
    }
}

131. 分割回文串

131. 分割回文串

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]

回溯算法

class Solution {
    private boolean check(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
    private void backtrace(List<List<String>> result, List<String> temp, String s) {
        if (s.length() == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if (check(s, 0, i)) {
                temp.add(s.substring(0, i + 1));
                backtrace(result, temp, s.substring(i + 1));
                temp.remove(temp.size() - 1);
            }
        }
    }
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrace(result, new ArrayList<>(), s);
        return result;
    }
}

301. 删除无效的括号

301. 删除无效的括号

删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。

说明: 输入可能包含了除 ( 和 ) 以外的字符。

示例 1:

输入: "()())()"
输出: ["()()()", "(())()"]
示例 2:

输入: "(a)())()"
输出: ["(a)()()", "(a())()"]
示例 3:

输入: ")("
输出: [""]

回溯算法

class Solution {
    Set<String> set = new HashSet<>();
    int maxLen = 0;
    public List<String> removeInvalidParentheses(String s) {
        int rmLeft = 0, rmRight = 0;
        // 1、对于括号,有选和不选两种情况;对于字母,必须选
        // 2、用计数器维护字符串状态,"("则加一,")"则减一
        // 3、set去重
        // 4、提前计算应当删除的左括号或者右括号的数量,用于剪枝
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                rmLeft++;
            } else if (s.charAt(i) == ')'){
                if (rmLeft > 0) {
                    rmLeft--;
                } else {
                    rmRight++;
                }
            }
        }
        helper(s, 0, 0, new StringBuilder(), rmLeft, rmRight);
        return new ArrayList<>(set);
    }
    private void helper(String s, int idx, int count, StringBuilder path, int rmLeft, int rmRight) {
        if (count < 0 || rmLeft < 0 || rmRight < 0) {
            return;
        }
        if (idx == s.length()) {
            if (count == 0 && rmLeft == 0 && rmRight == 0) {
                if (path.length() >= maxLen) {
                    maxLen = path.length();
                    set.add(path.toString());
                }
            }
            return;
        }
        // 添加当前字符到path中
        char c = s.charAt(idx);
        path.append(c);
        if (c == '(') {
            helper(s, idx + 1, count + 1, path, rmLeft, rmRight);
        } else if (c == ')') {
            helper(s, idx + 1, count - 1, path, rmLeft, rmRight);
        } else {
            helper(s, idx + 1, count, path, rmLeft, rmRight);
        }
        // 不添加当前字符到path中
        path.deleteCharAt(path.length() - 1);
        if (c == '(') {
            helper(s, idx + 1, count, path, rmLeft - 1, rmRight);
        } else if (c == ')') {
            helper(s, idx + 1, count, path, rmLeft, rmRight - 1);
        }
    }
}

22. 括号生成

22. 括号生成

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"] 示例 2:

输入:n = 1 输出:["()"]

提示:

1 <= n <= 8

递归

  • 左右括号数为0,添加结果
  • 左右括号数相等,只能添加”(“
  • 左右括号数不相等,可以添加“(”也可以添加“)”
class Solution {
    ArrayList<String> result;
    public List<String> generateParenthesis (int n) {
        // write code here
        result = new ArrayList<>();
        if (n <= 0) {
            return result;
        }
        getParenthesis("", n, n);
        return result;
    }
    private void getParenthesis(String s, int left, int right) {
        if (left == 0 && right == 0) {
            result.add(s);
            return;
        }
        if (left == right) {
            getParenthesis(s + "(", left - 1, right);
        } else {
            if (left > 0) {
                getParenthesis(s + "(", left - 1, right);
            }
            getParenthesis(s + ")", left, right - 1);
        }
    }
}

37. 解数独

37. 解数独

编写一个程序,通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则:

数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。

Note:

给定的数独序列只包含数字 1-9 和字符 '.' 。 你可以假设给定的数独只有唯一解。 给定数独永远是 9x9 形式的。

回溯算法

详细题解见https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode/

class Solution {
    private int n = 3;
    private int N = n * n;
    private int[][] rows = new int[N][N+1];
    private int[][] cols = new int[N][N+1];
    private int[][] boxes = new int[N][N+1];
    private char[][] board;
    private boolean solved = false;
    private boolean checkPlace(int d, int row, int col) {
        int index = (row / n) * n + col / n;
        return rows[row][d] + cols[col][d] + boxes[index][d] == 0;
    }
    private void placeNumber(int d, int row, int col) {
        int index = (row / n) * n + col / n;
        rows[row][d]++;
        cols[col][d]++;
        boxes[index][d]++;
        board[row][col] = (char)(d + '0');
    }
    private void removeNumber(int d, int row, int col) {
        int index = (row / n) * n + col / n;
        rows[row][d]--;
        cols[col][d]--;
        boxes[index][d]--;
        board[row][col] = '.';
    }
    private void placeNextNumber(int row, int col) {
        if (row == N - 1 && col == N - 1) {
            solved = true;
        } else {
            if (col == N - 1) {
                backtrack(row + 1, 0);
            } else {
                backtrack(row, col + 1);
            }
        }
    }
    private void backtrack(int row, int col) {
        if (board[row][col] == '.') {
            for (int d = 1; d <= N; d++) {
                if (checkPlace(d, row, col)) {
                    placeNumber(d, row, col);
                    placeNextNumber(row, col);
                    if (!solved) {
                        removeNumber(d, row, col);
                    }
                }
            }
        } else {
            placeNextNumber(row, col);
        }
    }
    public void solveSudoku(char[][] board) {
        this.board = board;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                char num = board[i][j];
                if (num != '.') {
                    int d = Character.getNumericValue(num);
                    placeNumber(d, i, j);
                }
            } 
        }
        backtrack(0, 0);
    }
}

还有一种效率更高的方法,选择的格子('.')在一行、一列和一个九宫格中可选数字最少的格子开始填数字。这样能更快找到结果。

剪枝条件:我们应该选择的格子('.')在行、列和个九宫格中可选数字最少的格子开始填数字。

对于每行、每列和每个9宫格都可以用9位的2进制数字来标识该行(列,9宫格)那些数字可以填。
    用1表示可填0表示不可填
    如例题中第行 :["5","3",".",".","7",".",".",".","."]
    第行中 有数字 5 3 7
                    下标    8  7  6  5  4  3  2  1  0
                二进制数    1  1  0  1  0  1  0  1  1
    因为5 3 7 已经有了,所以第1 2 4 6 8 9可填
    共有9行所以用9int表示行row[9],同理9col[9],99宫格cell[3][3]

class Solution {
    final int N = 9;
    int[] row = new int [N], col = new int [N];
    //ones数组表示0~2^9 - 1的整数中二进制表示中1的个数:如ones[7] = 3 ones[8] = 1
    //map数组表示2的整数次幂中二进制1所在位置(从0开始) 如 map[1] = 0,map[2] = 1, map[4] = 2
    int[] ones = new int[1 << N], map = new int[1 << N];
    int[][] cell = new int[3][3]; 
    public void solveSudoku(char[][] board) {
        init();
        int cnt = fill_state(board);
        dfs(cnt, board);
    }
    void init(){
        for(int i = 0; i < N; i++) row[i] = col[i] = (1 << N) - 1; 
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                cell[i][j] = (1 << N) - 1;
        //以上2个循环把数组的数初始化为二进制表示8个1,即一开始所以格子都可填
        for(int i = 0; i < N; i++) map[1 << i] = i;
        //统计0~2^9 - 1的整数中二进制表示中1的个数
        for(int i = 0; i < 1 << N; i++){
            int n = 0;
            for(int j = i; j != 0; j ^= lowBit(j)) n++;
            ones[i] = n;
        }
    }
    int fill_state(char[][] board){
        int cnt = 0;    //统计board数组空格('.')的个数
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(board[i][j] != '.'){
                    int t = board[i][j] - '1';
                    //数独中 i,j位置为数组下标,修改row col cell数组中状态
                    change_state(i, j, t);  
                }else cnt++;
            }
        }
        return cnt;
    }
    boolean dfs(int cnt, char[][] board){
        if(cnt == 0) return true;
        int min = 10, x = 0, y = 0;
        //剪枝,即找出当前所以空格可填数字个数最少的位置 记为x y
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(board[i][j] == '.'){
                    int k = ones[get(i, j)];
                    if(k < min){
                        min = k;
                        x = i;
                        y = j;
                    }
                }
            }
        }
        //遍历当前 x y所有可选数字
        for(int i = get(x, y); i != 0; i ^= lowBit(i)){
            int t = map[lowBit(i)];
            
            change_state(x, y, t);
            board[x][y] = (char)('1' + t);
            
            if(dfs(cnt - 1, board)) return true;
            
            //恢复现场
            change_state(x, y, t);
            board[x][y] = '.';
        }
        return false;
    }
    void change_state(int x, int y, int t){
        row[x] ^= 1 << t;
        col[y] ^= 1 << t;
        cell[x / 3][y / 3] ^= 1 << t;
    }
    //对维护数组x行,y列的3个集合(行、列、九宫格)进行&运算
    //就可以获得可选数字的集合(因为我们用1标识可填数字)
    int get(int x, int y){
        return row[x] & col[y] & cell[x / 3][y / 3];
    }
    int lowBit(int x){
        return -x & x;
    }
}
//作者:ri-mu-tu-yuan-12

51. N皇后

51. N 皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。 上图为 8 皇后问题的一种解法。

给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4 输出: [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."],

["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。

回溯算法

在 n*n 的矩阵中摆放 n 个皇后,并且每个皇后不能在同一行,同一列,同一对角线上,求所有的 n 皇后的解。

一行一行地摆放,在确定一行中的那个皇后应该摆在哪一列时,需要用三个标记数组来确定某一列是否合法,这三个标记数组分别为:列标记数组、45 度对角线标记数组和 135 度对角线标记数组。

45 度对角线标记数组的长度为 2 * n - 1,通过下图可以明确 (r, c) 的位置所在的数组下标为 r + c。 135 度对角线标记数组的长度也是 2 * n - 1,(r, c) 的位置所在的数组下标为 n - 1 - (r - c)。

class Solution {
    private List<List<String>> result;
    private char[][] nQueens;
    private boolean[] colUsed;
    private boolean[] diagonal1; //45度对角线
    private boolean[] diagonal2; //135度对角线
    private int n;
    private void backtrack(int row) {
        if (row == n) {
            List<String> temp = new ArrayList<>();
            for (char[] chars : nQueens) {
                temp.add(new String(chars));
            }
            result.add(temp);
            return;
        }
        for (int col = 0; col < n; col++) {
            int index1 = col + row; //45度对角线索引
            int index2 = n - 1 - (row - col); //135度对角线索引
            if (colUsed[col] || diagonal1[index1] || diagonal2[index2]) {
                continue;
            }
            nQueens[row][col] = 'Q';
            colUsed[col] = diagonal1[index1] = diagonal2[index2] = true;
            backtrack(row + 1);
            colUsed[col] = diagonal1[index1] = diagonal2[index2] = false;
            nQueens[row][col] = '.';
        }
    }
    public List<List<String>> solveNQueens(int n) {
        result = new ArrayList<>();
        nQueens = new char[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(nQueens[i], '.');
        }
        colUsed = new boolean[n];
        diagonal1 = new boolean[2 * n - 1];
        diagonal2 = new boolean[2 * n - 1];
        this.n = n;
        backtrack(0);
        return result;
    }
}