代码随想录 Day-19（回溯算法）

目录

思路

力扣题目 216.组合总和三

解法

优化分析

优化后的解法

力扣题目 17.电话号码的字母组合

思路分析

解法

力扣题目 131.分割回文串

错误的解法（可以自己debug一下，就知道错在哪里）

错误分析

正确的解法

回溯算法的小总结

思路

组合问题是选位置不同的数，分割问题是选位置不同的缝插进去，都是找位置，本质是相同的

力扣题目 216.组合总和三

解法

一拿到题目，仿照力扣77往上写，但是需要注意的是当前path的总和currentSum一定注意变化，以及起始位置是 i+1。

List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new LinkedList<>(); int currentSum = 0; public List<List<Integer>> combinationSum3(int k, int n) { backTracking(k, n, 1, currentSum); return res; } private void backTracking(int k, int sum, int start, int currentSum) { if (currentSum == sum && k == path.size()) { res.add(new ArrayList<>(path)); } else if (k < path.size() || currentSum > sum) { return; } for (int i = start; i <= 9; i++) { path.add(i); currentSum += i; backTracking(k, sum, i + 1, currentSum); Integer removeLast = path.removeLast(); currentSum -= removeLast; } }

优化分析

写完之后，需要考虑剪枝的优化。

当path里面的总和currentSum < 起始位置start，可以直接结束，因为是递增的，如果起始位置都大于currentSum，后面的肯定也大于，不用进行循环，直接就是弹出。

if (currentSum == sum && k == path.size()) {

res.add(new ArrayList<>(path));

} else if (k < path.size() || currentSum > sum) {

return;

}else if (sum - currentSum < start) {

return;

}

另外，考虑边界值的情况，如果说前面k个数相加已经大于要求的总和n值，那么直接结束，如下：

if (k * (k - 1) / 2 > sum) {

return;

}

if (currentSum == sum && k == path.size()) {

res.add(new ArrayList<>(path));

} else if (k < path.size() || currentSum > sum || sum - currentSum < start) {

return;

}

优化后的解法

List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new LinkedList<>(); public List<List<Integer>> combinationSum3(int k, int n) { int currentSum = 0; backTracking(k, n, 1, currentSum); return res; } private void backTracking(int k, int sum, int start, int currentSum) { if (k * (k - 1) / 2 > sum) { return; } if (currentSum == sum && k == path.size()) { res.add(new ArrayList<>(path)); } else if (k < path.size() || currentSum > sum || sum - currentSum < start) { return; } for (int i = start; i <= 9; i++) { path.add(i); currentSum += i; backTracking(k, sum, i + 1, currentSum); Integer removeLast = path.removeLast(); currentSum -= removeLast; } }

力扣题目 17.电话号码的字母组合

思路分析

组合回溯，那么应该怎么想呢？很容易想到，是不是可以通过一个数字对应一层的遍历，一层遍历里面就是对数字对应的字母的一个对应。怎么让数字对应字母呢？用集合？不用，可以直接用数组，组合下标对应数字，里面的值就是字母。

画一棵树表示回溯，更便于我们思考：

返回值和传入参数需要什么呢？不急，先确定其他两个步骤再回去确定传入参数。

终止条件：有一个n表示遍历层数，给的digits的数字个数就是对应的层数。当超过遍历层数就结束，因为这个时候已经拼接好字符串。这里和之前的组合有点区别，区别在于以前是用一个队列来记录path，这里直接用字符串记录。

if (n == digits.length()) { res.add(sb.toString()); return; }

单层遍历循环：在小于数字对应的字母长度里面遍历，将字母拼接到字符串之后进行递归，结束递归就去除刚才拼接的字符串。

for (int i = 0; i < map[digits.charAt(n) - '0'].length(); i++) { sb.append(map[digits.charAt(n) - '0'].charAt(i)); backtracking(digits, n + 1); sb.deleteCharAt(sb.length() - 1); }

终上可以得知，传入参数有：遍历层数的n，拼接字符串以及结果集用全局变量，不用传入参数，digits的要求遍历层数

void backtracking(String digits, int n)

解法

public List<String> letterCombinations(String digits) { backtracking(digits, 0); return res; } List<String> res = new ArrayList<>(); StringBuilder sb = new StringBuilder(); String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; void backtracking(String digits, int n) { if (n == digits.length()) { res.add(sb.toString()); return; } for (int i = 0; i < map[digits.charAt(n) - '0'].length(); i++) { sb.append(map[digits.charAt(n) - '0'].charAt(i)); backtracking(digits, n + 1); sb.deleteCharAt(sb.length() - 1); } }

解完之后，考虑是否有剪枝，边界值是什么？按照题目要求，边界值就是1，那么就是当digits只是一个数字，无非就是数字对应的字母，直接写：

public List<String> letterCombinations(String digits) { if (digits.length() == 1){ res.add(map[digits.charAt(0) - '0']); return res; } backtracking(digits, 0); return res; }

行不行？不行，因为这样子就是直接把对应的字母放进去，结果就是如下：[abc]，题目需要的返回结果是：[a, b, c]。因此这个题没什么剪枝的地方。

力扣题目 131.分割回文串

错误的解法（可以自己debug一下，就知道错在哪里）

class Solution { List<String> result = new ArrayList<>(); List<List<String> > ans = new ArrayList<>(); public List<List<String>> partition(String s) { backTracking(s,0); return ans; } private void backTracking(String s,int startIndex){ if(startIndex >= s.length()){ //收集结果集————终止条件 ans.add(result); return; } //单层运行的逻辑 for(int i=startIndex; i<s.length(); i++){ //如果是字符串就要记录 if(isPalindrome(s,startIndex,i)){ //切割字符串 String str = s.substring(startIndex,i+1); result.add(str); }else continue; backTracking(s,i+1); } } private boolean isPalindrome(String s,int start, int end){ for(int i=start,j=end; i<j; i++,j--){ if(s.charAt(i) != s.charAt(j)) return false; } return true; } }

错误分析

为什么错误呢？因为我的result是一个集合，里面的数据元素是累加的，所以在处理结果的时候会发生添加重复的数据元素。

所以解决方法应该是——用队列，每次将数据弹出去。

（即使将result设立为全局变量也无动于衷）

正确的解法

class Solution { List<List<String> > ans = new ArrayList<>(); Deque<String> result = new LinkedList<>(); public List<List<String>> partition(String s) { backTracking(s,0); return ans; } private void backTracking(String s,int startIndex){ if(startIndex >= s.length()){ //收集结果集————终止条件 ans.add(new ArrayList(result)); return; } //单层运行的逻辑 for(int i=startIndex; i<s.length(); i++){ //如果是字符串就要记录 if(isPalindrome(s,startIndex,i)){ //切割字符串 String str = s.substring(startIndex,i+1); result.add(str); }else continue; backTracking(s,i+1); //这里记得要pollLast才行 result.pollLast(); } } private boolean isPalindrome(String s,int start, int end){ for(int i=start,j=end; i<j; i++,j--){ if(s.charAt(i) != s.charAt(j)) return false; } return true; } }

牛比的大神可以做N皇后与解数独的题，小弟能力不够，到此为止，等我二刷再说

回溯算法的小总结