写在前面
对于回溯法，是一种特定的方法，会的人就会，不会的人想破脑袋也很难想出来。
其实回溯法和深度优先遍历 dfs 有很相似的地方。前者是利用后者再加上一步回溯删除来实现的。
今天就来看一下最基本的回溯法的例子。
对于组合问题，基本上都要有这种向后遍历，迭代调用的思想
78. Subsets 问题
问题分析
Subsets 问题很好理解，就是全排列问题。
给出一个数组 [1,2,3] ， 返回其全排列结果 [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]] 这包含7种情况的结果。
要想了解 BackTracing 算法，首先要明白 dfs 算法。
dfs 包含的参数有 4个，当前操作对象，起始位置，当前操作元素，最终结果。对应到该具体问题，就是
void dfs(int nums[], int start, List<Integer> ele, List<List<Integer>> res)
之后再 迭代调用。起始位置向后依次挪。
需要注意的两个点
- 在 res 中 添加 ele 时候，一定要用 new
实际上来说，很多这种添加新的元素进去，在 java 中都是要用 new 来 new 一个，不然这个对象一般来说会对应一个地址。导致最终添加不成功。 - dfs() 并没有返回类型，其是一个迭代调用。
-
迭代过程
dfs迭代过程
最终代码
public class Subsets {
public List<List<Integer>> subsets(int[] nums){
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (nums==null) return res;
Arrays.sort(nums);
dfs(nums, 0, new ArrayList<Integer>(),res);
return res;
}
public void dfs(int[] nums,int start,List<Integer> ele,List<List<Integer>> res){
res.add(new ArrayList<Integer>(ele)); // 这里一定要有 new,申请新的空间，相当于把数据复制了一份。
// 否则这里 res.add(ele) 在java中实际上是把最终ele指向地址的值传过来
// 因为后面有 remove 操作，最终的 ele 指向的地址总是空的。最后返回res也是空的。
for(int i=start;i<nums.length;i++){
ele.add(nums[i]);
dfs(nums,i+1,ele,res);
ele.remove(ele.size()-1); // 回溯 删除最后一个元素
}
}
public static void main(String args[]){
int a[]={1,2,3};
Subsets s = new Subsets();
System.out.println(s.subsets(a));
}
}
784. Letter Case Permutation 问题
给出字母的大小写所有的排列组合。
"ab"==> "ab", "Ab","aB","AB"
这个问题，貌似比上面回溯法的问题要简单一些。两个题目的解题思想是类似的，都是向后遍历。
这个题目中，向后遍历到某一个字符时候，如果这个字符是字母，那就进行操作嘛，换成大写/小写，继续向后遍历。直到遍历到最后一个，把当前结果添加到最终结果。
注意的点
- helper 函数实际上是对每一个位置的每一个字符进行操作。如果操作到了最后一个字符，就将结果加入到最后的res中。
- 添加元素是要用 new
跟上面说的那个一样的，添加新的都是要用 new
代码
class Solution {
public List<String> letterCasePermutation(String S) {
List<String> res = new ArrayList<>();
helper(res,S.toCharArray(),0);
return res;
}
// 这个函数自动向下操作，直到遍历完字符串
public void helper(List<String> res, char[] arr, int index){
if(index == arr.length){
// 遍历完了，达到长度了
res.add(new String(arr));
}else {
// 数字的话，直接跳过做下一个
if(Character.isDigit(arr[index])){
helper(res,arr,index+1);
}
// 如果是letter的话，我们就要加大小写了
else {
// 注意这里两种分支都有。大小写都有
arr[index] = Character.toUpperCase(arr[index]);
helper(res, arr, index+1);
arr[index] = Character.toLowerCase(arr[index]);
helper(res, arr, index+1);
}
}
}
}
其他思路
其实上面写的这个思路和回溯法还是有一定的区别的，上面的方法更多的是一种迭代的思路，并没有用到回溯的思想。所谓回溯，就和第一个例子一样，是一定要删除末尾元素的。
这里同样我们可以用一个 StringBuilder 来作为一个ele，遍历原始 s 中的每一个字符，大小写是两种情况，都向 ele 中添加。直到遍历完s中的字符。然后回删，这里根据题目意思，可能会有一些非字母的字符，所以回删的时候一定要注意，如果遇到非字母的字符，就直接删，直到第一个字母字符出现时候，才是回删元素。
代码如下。
package BackTracing;
// 题目要求，给定一个字符串，要求返回这个字符串的所有大小写组合结果。
// 这个比较简单，还是采用深度遍历，向后循环，一直到达到末尾长度的时候进行返回。
import java.util.ArrayList;
import java.util.List;
public class LetterCasePermutation {
public List<String> permutation(String s) {
List<String> res = new ArrayList<>();
dfs(s, 0, new StringBuilder(), res);
return res;
}
private void dfs(String s, int index, StringBuilder ele, List<String> res) {
if (index == s.length()) {
res.add(new String(ele));
return;
} else {
// 如果是字母的话
if (Character.isLetter(s.charAt(index))) {
ele.append(Character.toUpperCase(s.charAt(index)));
dfs(s, index + 1, ele, res);
// 回溯，在函数返回之后，删除后面的元素。
while (Character.isDigit(ele.charAt(ele.length()-1))){
ele.deleteCharAt(ele.length() - 1);
}
ele.deleteCharAt(ele.length() - 1);
ele.append(Character.toLowerCase(s.charAt(index)));
dfs(s, index + 1, ele, res);
while (Character.isDigit(ele.charAt(ele.length()-1))){
ele.deleteCharAt(ele.length() - 1);
}
ele.deleteCharAt(ele.length() - 1);
} else {
ele.append(s.charAt(index));
dfs(s, index + 1, ele, res);
}
}
}
public static void main(String args[]) {
String test = "a1b2c";
LetterCasePermutation letterCasePermutation = new LetterCasePermutation();
System.out.println(letterCasePermutation.permutation2(test));
}
}
网友评论