昆山市住房和建设局网站,wordpress 图片模糊,摄影网站网页设计,佛山企业模板建站来源0x3f#xff1a;https://space.bilibili.com/206214 回溯分为【子集型回溯】【组合型回溯】【排列型回溯】 文章目录回溯基本概念[17. 电话号码的字母组合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)子集型回溯#xff08;分割问题也可以看… 来源0x3fhttps://space.bilibili.com/206214 回溯分为【子集型回溯】【组合型回溯】【排列型回溯】 文章目录回溯基本概念[17. 电话号码的字母组合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)子集型回溯分割问题也可以看作枚举分割点子集型[78. 子集](https://leetcode.cn/problems/subsets/)方法一输入的视角每个节点可以选择选和不选方法二答案的角度枚举第一个数选谁、第二个数选谁[131. 分割回文串](https://leetcode.cn/problems/palindrome-partitioning/)思路设每两个相邻字符间有逗号枚举每个逗号结束位置。这样就变成了[78. 子集]问题[784. 字母大小写全排列](https://leetcode.cn/problems/letter-case-permutation/)[93. 复原 IP 地址](https://leetcode.cn/problems/restore-ip-addresses/)组合型回溯剪枝技巧[77. 组合](https://leetcode.cn/problems/combinations/)[216. 组合总和 III](https://leetcode.cn/problems/combination-sum-iii/)[22. 括号生成](https://leetcode.cn/problems/generate-parentheses/)排列型回溯棋盘问题也是排列型回溯[46. 全排列](https://leetcode.cn/problems/permutations/)[51. N 皇后](https://leetcode.cn/problems/n-queens/)回溯基本概念
回溯三问
1、当前操作
2、子问题
3、下一个子问题
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}17. 电话号码的字母组合
难度中等2314
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2
输入digits
输出[]示例 3
输入digits 2
输出[a,b,c]提示
0 digits.length 4digits[i] 是范围 [2, 9] 的一个数字。
回溯三问
1、当前操作 枚举 path[i] 要填入的字母
2、子问题 构造字符串i 的部分
3、下一个子问题 构造字符串 i1 的部分
class Solution {private static final String[] arr new String[]{, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};ListString res new ArrayList();public ListString letterCombinations(String digits) {if(digits.equals()) return res;dfs(digits, 0, new StringBuilder());return res;}public void dfs(String digits, int i, StringBuilder sb){if(i digits.length()){res.add(sb.toString());return;}String str arr[digits.charAt(i) - 0];for(int j 0; j str.length(); j){sb.append(str.charAt(j));dfs(digits, i1, sb);sb.deleteCharAt(sb.length()-1);}}
}子集型回溯分割问题也可以看作枚举分割点子集型
子集型回溯每个元素都可以选和不选
回溯三问
**1、当前操作**枚举第 i 个数选/不选
2、子问题 从下标 i 的数字中构造子集
3、下一个子问题 从下标 i1 的数字中构造子集 78. 子集
难度中等1931
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1
输入nums [1,2,3]
输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2
输入nums [0]
输出[[],[0]]提示
1 nums.length 10-10 nums[i] 10nums 中的所有元素 互不相同
题解
方法一输入的视角每个节点可以选择选和不选
class Solution {ListListInteger res new ArrayList();ListInteger cur;public ListListInteger subsets(int[] nums) {cur new ArrayList();dfs(nums, 0);return res;}// 每个节点可以选择选和不选public void dfs(int[] nums, int i){if(i nums.length){res.add(new ArrayList(cur));return;}dfs(nums, i1);cur.add(nums[i]);dfs(nums, i1);cur.remove(cur.size()-1);}
}方法二答案的角度枚举第一个数选谁、第二个数选谁
class Solution {ListListInteger res new ArrayList();ListInteger cur;public ListListInteger subsets(int[] nums) {cur new ArrayList();dfs(nums, 0);return res;}// 每个节点可以选择选和不选public void dfs(int[] nums, int i){// 关键在这里 递归入口每次记录答案res.add(new ArrayList(cur));if(i nums.length){return;}for(int j i; j nums.length; j){cur.add(nums[j]);dfs(nums, j1);cur.remove(cur.size()-1);}}
}131. 分割回文串
难度中等1387
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1
输入s aab
输出[[a,a,b],[aa,b]]示例 2
输入s a
输出[[a]]提示
1 s.length 16s 仅由小写英文字母组成
思路设每两个相邻字符间有逗号枚举每个逗号结束位置。这样就变成了[78. 子集]问题
方法二答案的角度枚举字串结束位置
class Solution {ListListString res new ArrayList();ListString cur;public ListListString partition(String s) {cur new ArrayList();dfs(s, 0);return res;}public void dfs(String s, int i){if(i s.length()){res.add(new ArrayList(cur));return;}//枚举字串结束位置(设以j结尾是否符合要求)for(int j i; j s.length(); j){//判断一下[i, j] 部分是否为回文串String str s.substring(i, j1);if(isrev(str)){cur.add(str);dfs(s, j1);cur.remove(cur.size()-1);}}}public boolean isrev(String str){int left 0, right str.length()-1;while(left right){if(str.charAt(left) ! str.charAt(right))return false;left; right--;}return true;}
}784. 字母大小写全排列
难度中等515
给定一个字符串 s 通过将字符串 s 中的每个字母转变大小写我们可以获得一个新的字符串。
返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
示例 1
输入s a1b2
输出[a1b2, a1B2, A1b2, A1B2]示例 2:
输入: s 3z4
输出: [3z4,3Z4]提示:
1 s.length 12s 由小写英文字母、大写英文字母和数字组成
题解
DFS 回溯 看到题目要求组合或者集合马上想到可以用回溯法
回溯法本来是说对于每个元素都先考虑放它的情况再考虑不放它的情况
放在这道题的背景里就是对于每个字母先考虑放它再考虑放它的另一种大小写形式。
class Solution {ListString res new ArrayList();public ListString letterCasePermutation(String s) {dfs(s, 0, new StringBuilder());return res;}public void dfs(String s, int i, StringBuilder sb){if(i s.length()){res.add(new String(sb.toString()));return;}// 不改sb.append(s.charAt(i));dfs(s, i1, sb);sb.deleteCharAt(sb.length()-1);//改if(s.charAt(i) a s.charAt(i) z){sb.append((char)(s.charAt(i) - 32));dfs(s, i1, sb);}else if(s.charAt(i) A s.charAt(i) Z){sb.append((char)(s.charAt(i) 32));dfs(s, i1, sb);}if((s.charAt(i) a s.charAt(i) z) || (s.charAt(i) A s.charAt(i) Z))sb.deleteCharAt(sb.length()-1);}
}93. 复原 IP 地址
难度中等1146收藏分享切换为英文接收动态反馈
有效 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 . 分隔。
例如0.1.2.201 和 192.168.1.1 是 有效 IP 地址但是 0.011.255.245、192.168.1.312 和 192.1681.1 是 无效 IP 地址。
给定一个只包含数字的字符串 s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s 中插入 . 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1
输入s 25525511135
输出[255.255.11.135,255.255.111.35]示例 2
输入s 0000
输出[0.0.0.0]示例 3
输入s 101023
输出[1.0.10.23,1.0.102.3,10.1.0.23,10.10.2.3,101.0.2.3]提示
1 s.length 20s 仅由数字组成
class Solution {ListString res new ArrayList(); ListString tmp new ArrayList();public ListString restoreIpAddresses(String s) {dfs(s, 0);return res;}public void dfs(String s, int begin){if(tmp.size() 4 begin ! s.length()) return;if(tmp.size() 4 begin s.length()){res.add(String.join(.,tmp));return;}//枚举分割点for(int j begin; j s.length() j begin3; j){String str s.substring(begin, j1);// 每个整数位于 0 到 255 之间组成if(Integer.parseInt(str) 255){// 不能含有前导 0if(str.length() 1 str.charAt(0) 0){return;}tmp.add(str);dfs(s, j1);tmp.remove(tmp.size()-1);}else{return;}}}
}组合型回溯剪枝技巧
77. 组合
难度中等1284
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1
输入n 4, k 2
输出
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]示例 2
输入n 1, k 1
输出[[1]]提示
1 n 201 k n
class Solution {ListListInteger res new ArrayList();ListInteger cur new ArrayList();int n, k;public ListListInteger combine(int _n, int _k) {n _n;k _k;dfs(1);return res;}public void dfs(int i){if(cur.size() k){ // d 0res.add(new ArrayList(cur));return;}for(int j i; j n - (k - cur.size()) 1 ; j){cur.add(j);dfs(j1);cur.remove(cur.size() - 1);}}
}相同方式倒着遍历的写法
class Solution {ListListInteger res new ArrayList();ListInteger cur new ArrayList();int n, k;public ListListInteger combine(int _n, int _k) {n _n; k _k;dfs(n);return res;}public void dfs(int i){int d k - cur.size();// 还要选 d 个数if(d 0){ res.add(new ArrayList(cur));return;}for(int j i; j d; j--){cur.add(j);dfs(j-1);cur.remove(cur.size() - 1);}}
}216. 组合总和 III
难度中等622
找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
示例 1:
输入: k 3, n 7
输出: [[1,2,4]]
解释:
1 2 4 7
没有其他符合的组合了。示例 2:
输入: k 3, n 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 2 6 9
1 3 5 9
2 3 4 9
没有其他符合的组合了。示例 3:
输入: k 4, n 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字我们可以得到的最小和是1234 10因为10 1没有有效的组合。提示:
2 k 91 n 60
class Solution {ListListInteger res new ArrayList();ListInteger cur new ArrayList();int k;public ListListInteger combinationSum3(int _k, int n) {k _k;dfs(9, n);return res;}public void dfs(int i, int target){int d k - cur.size();// 还要选 d 个数//剪枝// 首项末项 *项数 /2 仍然比target小就不用递归了if(target 0 || target (i*2 - d 1) * d / 2)return; // d 0 , (i*2 - d 1) * d / 2也是等于0的就不用判断target 0 了if(d 0){ res.add(new ArrayList(cur));return;}for(int j i; j d; j--){cur.add(j);dfs(j-1, target-j);cur.remove(cur.size() - 1);}}
}22. 括号生成
难度中等3091
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例 1
输入n 3
输出[((())),(()()),(())(),()(()),()()()]示例 2
输入n 1
输出[()]提示
1 n 8
class Solution {int n;char[] path;ListString res new ArrayList();public ListString generateParenthesis(int n) {this.n n;path new char[n * 2];dfs(0, 0);return res;}public void dfs(int i, int open){if(i n * 2){res.add(new String(path));}if(open n){ // 可以填左括号path[i] (;dfs(i1, open1);}if(i - open open){ // 不可以填左括号了只能填右括号}path[i] );dfs(i1, open);}}
}排列型回溯棋盘问题也是排列型回溯
排列型和组合型的区别组合中不能有{12} {21} 同时存在因为他们是相同的组合
46. 全排列
难度中等2411
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2
输入nums [0,1]
输出[[0,1],[1,0]]示例 3
输入nums [1]
输出[[1]]提示
1 nums.length 6-10 nums[i] 10nums 中的所有整数 互不相同
class Solution {ListListInteger res new ArrayList();ListInteger cur new ArrayList();boolean[] visit;public ListListInteger permute(int[] nums) {visit new boolean[nums.length];dfs(0, nums);return res;}public void dfs(int i, int[] nums){if(i nums.length){res.add(new ArrayList(cur));return;}for(int k 0; k nums.length; k){if(visit[k] false){visit[k] true;cur.add(nums[k]);dfs(i1, nums);cur.remove(cur.size()-1);visit[k] false;}}}}51. N 皇后
难度困难1648
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。
示例 1 输入n 4
输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]
解释如上图所示4 皇后问题存在两个不同的解法。示例 2
输入n 1
输出[[Q]]提示
1 n 9
题解https://leetcode.cn/problems/n-queens/solution/java-c-by-tizzi-i9j0/
class Solution {ListListString ans new ArrayList();int[] row;boolean[] cols, d, ud;int N;public ListListString solveNQueens(int n) {N n;cols new boolean[n];d new boolean[30];ud new boolean[30];row new int[n];// 用来保存第几行第几列放置Qdfs(0);return ans;}// col【】数组记录某列已经放过了皇后。col【i】 1代表第i列已经放了一个皇后。// d【】 数组来记录某正对角线已经放置过了皇后。// ud【】数组来记录某反对角线已经放置过了皇后。public void dfs(int i){if(i N){char[] arr new char[N];Arrays.fill(arr, .);ListString g new ArrayList();for(int j 0; j N; j){arr[row[j]] Q;g.add(new String(arr));arr[row[j]] .;}ans.add(g);return;}// 选择一个位置进行放置for(int j 0; j N; j){// 列对角线、反对角线判断if (!cols[j] !d[i j] !ud[N - i j]){cols[j] d[ij] ud[N-ij] true;row[i] j;dfs(i1);cols[j] d[ij] ud[N-ij] false;}}}
}
