https://leetcode-cn.com/tag/backtracking/
10. 正则表达式匹配难度困难（看了题解理解的，动态规划）
17. 电话号码的字母组合难度中等
22. 括号生成难度中等
37. 解数独难度困难(不会做)
39. 组合总和难度中等 [✔]
40. 组合总和 II难度中等 [✔]
44. 通配符匹配难度困难（看了题解理解的，动态规划）
46. 全排列难度中等 [✔]
47. 全排列 II难度中等 [✔]
51. N皇后难度困难
回溯代码的框架
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
10. 正则表达式匹配难度困难
给你一个字符串
s和一个字符规律p，请你来实现一个支持'.'和'*'的正则表达式匹配。
'.'匹配任意单个字符
'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个字符串s的，而不是部分字符串。
说明:
s可能为空，且只包含从a-z的小写字母。
p可能为空，且只包含从a-z的小写字母，以及字符.和*。
思路：动态规划
class Solution {//执行用时 :3 ms, 在所有 Java 提交中击败了90.91%的用户
public boolean isMatch(String s, String p) {
//dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;
//初始化
for(int j=1;j<p.length()+1;j++){
if(j == 1) //比如p = b， 只有一个元素，这时候一定是false
dp[0][j] = false;
if(p.charAt(j-1) == '*' && dp[0][j-2])//比如p = b*，这时看dp[0][j-2]是否为true
dp[0][j] = true;
}
for(int i=1;i<=s.length();i++){
for(int j=1;j<=p.length();j++){
//最简单的情况，字符相等或者p的字符是‘.'
if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.')
dp[i][j] = dp[i-1][j-1];
else if(p.charAt(j-1) == '*'){
//如果p的*前边的字符和s当前字符相等或者p的字符是‘.'
//三种可能
//匹配0个，比如aa aaa* dp[i][j]=dp[i][j-2]
//匹配1个，比如aab aab* dp[i][j]=dp[i][j-1]
//匹配多个，比如aabb aab* 就看aab 和aab*是否能匹配上，即dp[i][j]=dp[i-1][j]
if(p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2)=='.'){
dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i][j-2];
}
//如果p的*前边的字符和s当前字符不相等或者p的字符不是‘.'
//那就把*和*前边一个字符都不要了
else{
dp[i][j] = dp[i][j-2];
}
}else{
dp[i][j] = false;
}
}
}
return dp[s.length()][p.length()];
}
}
17. 电话号码的字母组合难度中等
给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
class Solution {
public List<String> letterCombinations(String digits) {
if(digits == null || digits.length() == 0)
return new ArrayList<>();
List<String> res = new ArrayList<>();
if(digits.length() != 0)
backtrack(res,"",digits);
return res;
}
public void backtrack(List<String> res, String combination, String next_digit){
HashMap<String,String> map = new HashMap<>();
map.put("2","abc");
map.put("3","def");
map.put("4","ghi");
map.put("5","jkl");
map.put("6","mno");
map.put("7","pqrs");
map.put("8","tuv");
map.put("9","wxyz");
if(next_digit.length() == 0){
res.add(combination);
}else{
String digit = next_digit.substring(0,1);
String letters = map.get(digit);
for(int i = 0; i < letters.length(); i++){
String letter = letters.substring(i, i+1);
backtrack(res, combination + letter, next_digit.substring(1));
}
}
}
}
22. 括号生成难度中等
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 **有效的 **括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
思路：DFS不用回溯
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
if(n == 0)
return new ArrayList<>();
dfs(res, n, n, "");
return res;
}
/**
* @param res 结果集
* @param left 左括号还有几个可以使用
* @param right 右括号还有几个可以使用
* @param curStr 当前递归得到的结果
*/
public void dfs(List<String> res, int left, int right, String curStr){
if(left == 0 && right == 0)
res.add(curStr);
if(left > right) return;//这一步刚开始没考虑到，是剪枝
if(left > 0){
dfs(res, left - 1, right, curStr + "(");
}
if(right > 0){
dfs(res, left, right - 1, curStr + ")");
}
}
}
37. 解数独难度困难
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
（1）数字1-9在每一行只能出现一次。
（2）数字1-9在每一列只能出现一次。
（3）数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
空白格用'.'表示。
给定输入
输出结果
答案被标成红色。
Note:
- 给定的数独序列只包含数字
1-9和字符'.'。- 你可以假设给定的数独只有唯一解。
- 给定数独永远是
9x9形式的。
思路：回溯
https://leetcode-cn.com/problems/sudoku-solver/solution/hui-su-fa-jie-shu-du-by-i_use_python/自己对题解中部分还是不理解
class Solution {
public void solveSudoku(char[][] board) {
//三个布尔数组，表示在每行，每列，每个格子中，这个数字是否使用过
boolean[][] rowUsed = new boolean[9][10];
boolean[][] colUsed = new boolean[9][10];
boolean[][][] boxUsed = new boolean[3][3][10];
//初始化三个布尔数组，遍历board，表示在每行，每列，每个格子中，这个数字被使用过了
for(int row = 0; row < 9; row++){
for(int col = 0; col < 9; col++){
int num = board[row][col] - '0';
if(num >= 1 && num <= 9){
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[row/3][col/3][num] = true;
}
}
}
//填充数组
solveSudokuHelper(board, rowUsed, colUsed, boxUsed, 0, 0);
}
public boolean solveSudokuHelper(char[][] board, boolean[][] rowUsed, boolean[][] colUsed,boolean[][][] boxUsed, int row, int col){
// 边界校验, 如果已经填充完成, 返回true, 表示一切结束
if(col == 9){
col = 0;
row++;
if(row == 9){
return true;
}
}
if(board[row][col] == '.'){
for(int num = 1; num <= 9; num++){
boolean canUsed = !(rowUsed[row][num] || colUsed[col][num] || boxUsed[row/3][col/3][num]);
if(canUsed){
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[row/3][col/3][num] = true;
board[row][col] = (char)('0' + num);
if(solveSudokuHelper(board, rowUsed, colUsed, boxUsed, row, col + 1)){
return true;
}
board[row][col] = '.';
rowUsed[row][num] = false;
colUsed[col][num] = false;
boxUsed[row/3][col/3][num] = false;
}
}
}else{
return solveSudokuHelper(board, rowUsed, colUsed, boxUsed, row, col + 1);
}
return false;
}
}
39. 组合总和难度中等
给定一个无重复元素的数组
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的数字可以无限制重复被选取。
说明：
所有数字（包括target）都是正整数。
解集不能包含重复的组合。
示例 1：
输入：candidates =[2,3,6,7],target =7,
所求解集为：
[
[7],
[2,2,3]
]
思路：回溯
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();//存放结果集
backtrack(res, candidates, target, 0, new ArrayList<>());
return res;
}
public void backtrack(List<List<Integer>> res, int[] candidates, int target,int start, List<Integer> cur){
if(target == 0)
res.add(new ArrayList<>(cur));
for(int i = start; i < candidates.length; i++){
if(target < candidates[i]) continue;
List<Integer> list = new ArrayList<>(cur);
list.add(candidates[i]);
backtrack(res, candidates, target - candidates[i], i, list);
}
}
}
40. 组合总和 II难度中等339
给定一个数组
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]
]
思路：回溯
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();//存放结果集
Arrays.sort(candidates);
backtrack(res, candidates, target, 0, new ArrayList<>());
return res;
}
public void backtrack(List<List<Integer>> res, int[] candidates, int target,int start, List<Integer> cur){
if(target == 0)
res.add(new ArrayList<>(cur));
for(int i = start; i < candidates.length; i++){
if(target < candidates[i]) continue;
// 小剪枝，去除重复元素
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
List<Integer> list = new ArrayList<>(cur);
list.add(candidates[i]);
backtrack(res, candidates, target - candidates[i], i + 1, list);//i+1避免重复选取数组元素
}
}
}
44. 通配符匹配难度困难
给定一个字符串 (
s) 和一个字符模式 (p) ，实现一个支持'?'和'*'的通配符匹配。
'?'可以匹配任何单个字符。
'*'可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
（1）s可能为空，且只包含从a-z的小写字母。
（2）p可能为空，且只包含从a-z的小写字母，以及字符?和*。
示例 1:
输入:
s ="aa"
p ="a"
输出: false，解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s ="aa"
p ="*"
输出: true，解释:"*"可以匹配任意字符串。
示例 3:
输入:
s = "acdcb"
p = "a*c?b"
输出: false
思路：动态规划
class Solution {//执行用时 :36 ms, 在所有 Java 提交中击败了48.23%的用户
public boolean isMatch(String s, String p) {
int slen = s.length();
int plen = p.length();
//dp[i][j] : 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配
boolean[][] dp = new boolean[slen+1][plen+1];
//初始化
dp[0][0] = true;
for(int j=1;j<=plen;j++){
if(p.charAt(j-1) == '*' && dp[0][j-1])
dp[0][j] = true;//s 为空，与 p 匹配
}
for(int i=1;i<=slen;i++){
for(int j=1;j<=plen;j++){
if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?')
dp[i][j] = dp[i-1][j-1];
else if(p.charAt(j-1) == '*')
//dp[i][j - 1] 表示 * 代表的是空字符，例如 ab, ab*
//dp[i - 1][j] 表示 * 代表的是非空字符，例如 abcd, ab*
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
return dp[slen][plen];
}
}
46. 全排列难度中等
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
思路：回溯
class Solution {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if(len == 0) return res;
boolean[] used = new boolean[len];
List<Integer> path = new ArrayList<>();
backtrack(res, nums, len, 0, used, path);
return res;
}
public void backtrack(List<List<Integer>> res, int[] nums, int len,
int depth, boolean[] used, List<Integer> path){
if(depth == len)
res.add(new ArrayList<>(path));
for(int i = 0; i < len; i++){
if(!used[i]){
path.add(nums[i]);
used[i] = true;
backtrack(res, nums, len, depth + 1, used, path);
//状态重置，回溯
used[i] = false;
path.remove(path.size() - 1);
}
}
}
}
47. 全排列 II难度中等
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
思路：回溯
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if(len == 0) return res;
Arrays.sort(nums);//相比上题
boolean[] used = new boolean[len];
List<Integer> path = new ArrayList<>();
backtrack(res, nums, len, 0, used, path);
return res;
}
public void backtrack(List<List<Integer>> res, int[] nums, int len,
int depth, boolean[] used, List<Integer> path){
if(depth == len)
res.add(new ArrayList<>(path));
for(int i = 0; i < len; i++){
if (used[i]) {
continue;
}
//剪枝
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
path.add(nums[i]);
used[i] = true;
backtrack(res, nums, len, depth + 1, used, path);
//状态重置，回溯
used[i] = false;
path.remove(path.size() - 1);
}
}
}
51. N皇后难度困难
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中'Q'和'.'分别代表了皇后和空位。
提示：
皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步，可进可退。（引用自 百度百科 - 皇后 ）
思路：回溯
class Solution {
// 定义三个布尔数组，表示列和主副对角线的元素是否使用过
private boolean[] col;
private boolean[] dia1;
private boolean[] dia2;
private List<List<String>> ans = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
col = new boolean[n];
dia1 = new boolean[2 * n - 1]; // 对角线个数为 2 * n - 1
dia2 = new boolean[2 * n - 1];
// 定义每行的元素个数
List<Integer> list = new LinkedList<>();
// 回溯寻找符合要求的每组解
putQueen(n, 0, list);
return ans;
}
// row 代表当前访问的行数,最多到 n; list 用来存放满足题意的一种情况
private void putQueen(int n, int row, List<Integer> list) {
// 如果遍历到了最后一行，即代表已经找出一组解出来
if (row == n) {
// 将找到的一组解转化为棋盘格的形式后再放入 ans
ans.add(changeBoard(n, list));
return;
}
// 遍历当前 row 行的所有位置(从前往后依次遍历)
for (int i = 0; i < n; i++) {
// row + i 表示横纵坐标相加
// row - i + n - 1 表示横纵坐标之差
// 如果当前位置元素与他同一列，同一主副对角线上没有重复元素
if (!col[i] && !dia1[row + i] && !dia2[row - i + n - 1]) {
// 则该位置即皇后放置的位置，放入 list 存储位置信息，并标记为 true
list.add(i);
// 此时在该元素所在的列和主副对角线上就不能在遍历找到其他元素了
// 即标记为 true
col[i] = true;
dia1[row + i] = true;
dia2[row - i + n - 1] = true;
// 接着递归寻找下一行
putQueen(n, row + 1, list);
// 遍历完后再退出标记
col[i] = false;
dia1[row + i] = false;
dia2[row - i + n - 1] = false;
// 回退上一格子(回溯)
list.remove(list.size() - 1);
}
}
return;
}
// 将找到的一组解转化为棋盘格形式存储
private List<String> changeBoard(int n, List<Integer> list) {
List<String> tmp = new ArrayList<>();
for (int i = 0; i < n; i++) {
char[] ch = new char[n];
Arrays.fill(ch, '.'); // 初始化 ch 中所有位置元素为 ‘.’
// 将 row 中已经确定下来的 Queen 位置改为 ‘Q’
ch[list.get(i)] = 'Q';
// 然后放入 tmp 中
tmp.add(new String(ch));
}
return tmp;
}
}
