回溯算法

基本概念

回溯的本质是通过深度遍历的方式找到所有满足条件的可能解。遇到排列组合类的问题，应该联想到通过回溯来解决。常见的问题类似给定一个集合，需要从中挑出一定数量的元素，凑成满足某个条件的解。问一共能找到多少个这样的解，或者列举出所有满足条件的解。

基础实现

回溯是有一个基础模版的，在此基础上做微调来解决不同的问题。

def bacakTrace(当前元素，当前拼接结果，其他){
  if(当前拼接结果满足退出条件(数量达到要求)){
    if(是一个可用的解){
      加入结果集
    }
    return；
  }
  for(其他元素){
    if(当前元素可用){
      本次处理的元素
      拼接结果+本次处理元素
      backTrace(本次处理元素，拼接结果，其他)
      拼接结果-本次处理元素
    }
  }
}

拿基础的一个求组合数（lc216）的代码为例子，对照上面的模版：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        int[] used = new int[9];
        List<Integer> current = new ArrayList<>();
        backTrace(1,current,k,n,used);
        return res;
    }

    public void backTrace(int i, List<Integer> current, int k, int n, int[] used){
        if(current.size() == k){
            if(n == 0){
                res.add(new ArrayList<>(current));
            }
            return;
        }
        for(int j=i;j<=9;j++){
            if(used[j-1]==0){
                current.add(j);
                used[j-1] = 1;
                backTrace(j,current,k,n-j,used);
                used[j-1] = 0;
                current.remove(current.size()-1);
            }
        }
    }
}

实现细节

组合数和排列数都可以用回溯来做，其区别就是是否去重。

对于组合数，需要去重，因为结果1，2，3和3，2，1是相同的组合数

对于排列数，不需要去重，因为1，2，3和3，2，1不同

如何控制去重有两种方式：

• 保证结果内部顺序，通过Set承接结果
• 当每个元素只能用一次时，回溯过程跳过已经回溯过的元素，从下一个开始（传入i，j=i的意义），这样是不会有重复元素的。

  进阶情况

lc51 经典的N皇后问题，标准的回溯问题，复杂点在于判断当前这个位置可不可用。即模版中的第9行的判断比较复杂。