基本的 BackTracing 回溯法

写在前面

对于回溯法，是一种特定的方法，会的人就会，不会的人想破脑袋也很难想出来。
其实回溯法和深度优先遍历 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)

之后再 迭代调用。起始位置向后依次挪。

需要注意的两个点

1. 在 res 中 添加 ele 时候，一定要用 new
   实际上来说，很多这种添加新的元素进去，在 java 中都是要用 new 来 new 一个，不然这个对象一般来说会对应一个地址。导致最终添加不成功。
2. dfs() 并没有返回类型，其是一个迭代调用。

3. 迭代过程

   
   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"
这个问题，貌似比上面回溯法的问题要简单一些。两个题目的解题思想是类似的，都是向后遍历。
这个题目中，向后遍历到某一个字符时候，如果这个字符是字母，那就进行操作嘛，换成大写/小写，继续向后遍历。直到遍历到最后一个，把当前结果添加到最终结果。

注意的点

1. helper 函数实际上是对每一个位置的每一个字符进行操作。如果操作到了最后一个字符，就将结果加入到最后的res中。
2. 添加元素是要用 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));
    }
}