回溯算法

基本描述

leetcode定义回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

与递归，DFS关系 回溯算法是个思想，回溯法的实现方法有两种：递归和递推（也称迭代，非递归）。一般来说，一个问题两种方法都可以实现，只是在算法效率和设计复杂度上有区别。与DFS的整体过程是一致的，都是一条路走到底，不撞南墙不回头。回溯算法是枚举，枚举的方式是深度优先搜索，回溯算法需要在深度优先搜索的同时，把临时路径一直传递下去。 回溯算法三元素

选择。对于每个特定的解，每一步怎么构建，有多个选择，按照某种顺序依次尝试当前的每个选择，一般是通过多个if或者for循环来排列。
条件。对于每一个选择，只有符合条件才能继续向前扩展，如果不符合条件，就要回溯。
结束。当到达一个特定结束条件时，一个解就出来了。可以另外写一个isSolution函数来进行判断是否可行解。有时候还需要构建一个数据结构，把符合要求的解存起来，便于当得到所有解后，把解空间输出来。这个数据结构必须是全局的，可以作为参数之一传递给递归函数，也可以是成员变量。
概念及原理

这类问题的解可表示成一个n元组（x0,x1,…,xn-1），求满足约束条件的可行解，或进一步求使目标函数取最大（或最小）值的最优解问题，这类问题一般都可以用回溯法求解。回溯法通过使用约束函数和限界函数来压缩需要实际生成的状态空间树的结点数，从而大大节省问题求解时间。
- 子集数（Subset Trees）：当所给问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树。
- 排列树（Permutation Trees）：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。

解空间树的三种节点

活节点：还有子节点未被搜索过的节点
扩展节点：当前正在尝试纵深方向搜索的节点
死节点：没有子节点或者所有子节点都被搜索过

确定了解空间的组织结构后，回溯法从根节点出发，以深度优先的方式搜索整个解空间。这个开始节点成为一个活节点，同时也成为当前的扩展节点。在当前的扩展节点处，搜索向纵深方向移至一个新节点。这个新节点就成为一个新的活节点，并成为当前扩展节点。如果在当前扩展节点处不能再向纵深方向移动，则当前的扩展节点就成为死节点。此时，应往回移动即回溯至最近的一个活节点处，并使这个活节点成为当前的扩展节点。回溯法即以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活节点为止。 以0/1背包问题为例

public class Knapsack {
    private int curWeight;

    private int curValue;

    private int bestValue;

    private final int CAPACTITY = 25;

    private final int NUM = 3;

    private int[] bestResult = new int[NUM];

    public void knapsack(int[] weights, int[] values) {
        //初始时从0开始搜索
        backtrack(weights, values, 0, new int[NUM]);
        for (int i = 0; i < NUM; i++) {
            System.out.println(bestResult[i]);
        }
        System.out.println(bestValue);
    }

    private void backtrack(int[] weights, int[] values, int index, int[] path) {
        if (index > NUM - 1) {//到达叶子节点，得到一个可行解
            if (curValue > bestValue) {//判断是否为最优解
                bestValue = curValue;//更新最优解
                for (int i = 0; i < NUM; i++) {
                    bestResult[i] = path[i];
                }
            }
            return;
        }
        //1,确定每一步的选择集，0/1背包问题每步的选择只有0和1
        for (int i = 0; i <= 1; i++) {
            //2,更新临时路径
            path[index] = i;
            //3，如果选择0，则直接向前扩展
            //4，如果选择1，并且没有超过容量，则可以继续扩展，否则剪枝
            if (curWeight + weights[index] * i <= CAPACTITY) {
                //4.1 更新当前值(做选择)
                curValue += values[index] * i;
                curWeight += weights[index] * i;
                //4.2 纵深扩展
                backtrack(weights, values, index + 1, path);
                //4.3 恢复当前值(撤销选择)，以便回溯
                curValue -= values[index] * i;
                curWeight -= weights[index] * i;
            }
        }
    }
}

通用解法

一般用递归实现，递归函数设计： 1、必须要有一个临时变量(初始时可以就直接传递一个字面量或者常量进去)传递不完整的解，表示截至当前解的情况，因为每一步选择后，暂时还没构成完整的解，这个时候这个选择的不完整解，也要想办法传递给递归函数。也就是，把每次递归的不同情况传递给递归调用的函数。【每一步的解的汇总信息传递下去】表示临时路径。 2、可以有一个全局变量，用来存储完整的每个解，一般是个集合容器（也不一定要有这样一个变量，因为每次符合结束条件，不完整解就是完整解了，直接打印即可）。【存储完整的解空间，也可以用类的属性】 3、最重要的一点，一定要在参数设计中，可以得到结束条件。一个选择是可以传递一个递增变量，也许是数组的长度，也许是数量，索引等等。【结束条件】 4、要保证递归函数返回后，状态可以恢复到递归前，以此达到真正回溯。【恢复状态：下一次递归前，把当前这一步的选择清除或者还原】回溯的意思就是要回去，递归函数自动保证了回去，但是我们设置的其他变量如果有必要的话也必须要回到原位。

通过递增变量或者临时路径进行扩展，看情况，一般递增变量扩展时增加1，临时路径扩展时尾部增加一步。路径代表已做过的选择，可以是索引值index，也可以是链表。做选择、扩展递归下一步、撤销选择。

伪代码：

void findSolutions(t, other params) :
    //1，结束条件，一轮搜索结束，得到一个可行解
    if (t > n) :
        displaySolution();
        return;
    for (val = first to last) : //2，做选择
        if (isValid(val, n)) : //3，剪枝
            applyValue(val, n); //4，应用选择
            findSolutions(n+1, other params); //5，向前纵向扩展
            removeValue(val, n); //6，撤销选择

leetcode回溯算法题解

leetcode例题

416.分割等和子集转化为[0/1背包问题]：

class Solution {
   public boolean canPartition(int[] nums) {
        if (nums.length <= 1) {
            return false;
        }
        int sum = 0;
        for (int element : nums) {
            sum += element;
        }
        if (sum % 2 != 0) {
            return false;
        }
        Arrays.sort(nums);
        return backtrack(nums.length - 1, sum / 2, nums);
    }

    public boolean backtrack(int index, int remainSum, int[] nums) {
        if (index <0 || nums[index] > remainSum) {
            return false;
        }
        if (nums[index] == remainSum) {
            return true;
        }

        for (int i = 1; i >= 0; i--) {//i++会超时
            remainSum -= nums[index] * i;
            if (backtrack(index - 1, remainSum, nums)) {
                return true;
            }
            remainSum += nums[index] * i;
        }
        return false;
    }
}

为了套用模板，写的不够简洁，有更简洁的写法。

254因子的组合与前一题的不同之处在于，单个解向量的元素个数是不确定的。

class Solution {
   private List<List<Integer>> results = new ArrayList<>();

    public List<List<Integer>> getFactors(int n) {
        if (n <= 3) {
            return results;
        }
        LinkedList<Integer> path = new LinkedList<>();
        path.add(1);
        backtrack(n, path);
        return results;
    }

    private void backtrack(int remain, LinkedList<Integer> path) {
        if (remain == 1) {
            List<Integer> result = new LinkedList<>();
            for (int ele : path) {
                if (ele != 1) {
                    result.add(ele);
                }
            }
            Collections.sort(result);
            if (!results.contains(result) && result.size() != 1) {
                results.add(result);
            }
            return;
        }
        for (int i = 2; i <= remain; i++) {
            if (remain % i != 0) {
                continue;
            }
            path.add(i);
            remain = remain / i;
            backtrack(remain, path);
            path.removeLast();
            remain = remain * i;
        }
    }
}

51. N皇后问题


public class NQueens {
    private List<List<String>> res = new LinkedList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        backtrack(0, board);
        return res;
    }

    /**
     * backtrack为标准的回溯法模板
     *
     * @param index 索引，或者已做选择的路径
     * @param board
     */
    private void backtrack(int index, char[][] board) {
        //结束条件为所有的皇后都已放置
        if (index == board.length) {
            res.add(chars2StrList(board));//把可行解加入到结果集
            return;
        }
        int cols = board[0].length;
        //选择列表为每一列
        for (int i = 0; i < cols; i++) {
            if (!isValid(board, index, i)) {//剪枝
                continue;
            }
            //做选择，在当前位置放置皇后
            board[index][i] = 'Q';
            //向纵深方向扩展一步
            backtrack(index + 1, board);
            //撤销选择
            board[index][i] = '.';
        }
    }

    private List<String> chars2StrList(char[][] board) {
        List<String> strList = new LinkedList<>();
        for (char[] row : board) {
            strList.add(String.valueOf(row));
        }
        return strList;
    }

    private boolean isValid(char[][] board, int row, int col) {
        //检查同一列有没有放置皇后
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        //检查左上角的对角线有没有放置皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        //检查右上角的对角线有没有放置皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

1087.字母切换

class Solution {
    public String[] expand(String S) {
        if (!S.contains("{")) {
            return new String[] {S};
        }
        String s = S.replaceAll("\\{", " ").replaceAll("}", " ").replaceAll(",", "");
        String[] strs = s.split(" ");
        List<String> list = new ArrayList<>();
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].length() != 0) {//"" length is 0
                list.add(strs[i]);
            }
        }

        List<String> listresult = new ArrayList<>();
        LinkedList<Character> path = new LinkedList<>();
        backtraceDfs(list, 0, path, listresult);

        Collections.sort(listresult);
        return listresult.toArray(new String[listresult.size()]);
    }

    void backtraceDfs(List<String> list, int index, LinkedList<Character> path, List<String> listresult) {

        if (index == list.size()) {
            StringBuilder builder = new StringBuilder();
            for (int k = 0; k < path.size(); k++) {
                builder.append(path.get(k));
            }
            listresult.add(builder.toString());

            return;
        }

        for (int j = 0; j < list.get(index).length(); j++) {
            path.add(list.get(index).charAt(j));
            backtraceDfs(list, index + 1, path, listresult);
            path.removeLast();
        }
    }
}

267.回文排列II

class Solution {
   private List<String> result = new ArrayList<>();

   public List<String> generatePalindromes(String s) {

        if (s.length() < 1) {
            return new ArrayList<String>();
        }
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            Character key = s.charAt(i);
            map.put(key, map.getOrDefault(key, 0) + 1);
        }
        Character ch = null;
        int size = 0;
        int count = 0;
        for (Character c : map.keySet()) {
            if (map.get(c) % 2 == 1) {
                map.put(c, map.get(c) - 1);
                ch = c;
                count++;
            }
            size += map.get(c) / 2;
        }
        if (count > 1) {
            return new ArrayList<String>();
        }
        char[] chars = new char[size];
        int i = 0;
        for (char c : map.keySet()) {
            for (int j = 0; j < map.get(c) / 2; j++) {
                chars[i++] = c;
            }
        }
        palindrome2(chars, new StringBuilder(), ch, new boolean[size]);
        return new ArrayList<>(result);
    }

    private void palindrome2(char[] chars, StringBuilder sb, Character ch, boolean[] visited) {
        if (sb.length() == chars.length) {
            StringBuilder temp = new StringBuilder(sb);
            StringBuilder reverse = new StringBuilder(sb).reverse();
            result.add(ch == null ? temp.append(reverse).toString() : temp.append(ch).append(reverse).toString());
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (visited[i]) {
                continue;
            }
            if (i > 0 && !visited[i - 1] && chars[i] == chars[i - 1]) {
                continue;
            }
            sb.append(chars[i]);
            visited[i] = true;
            palindrome2(chars, sb, ch, visited);
            sb.deleteCharAt(sb.length() - 1);
            visited[i] = false;
        }
    }

}

总结

回溯法思路的简单描述是：把问题的解空间转化成了图或者树的结构表示，定义解空间树，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。

贪心法和动态规划法都要求问题最优解具有最优子结构特性。贪心法求解还要求设计最优量度标准，但这并非易事，这时候可以用回溯。回溯法是比贪心法和动态规划法更一般的方法。

回溯法

年份	事件	相关论文
1960	R. J. Walker第一次尝试全面阐述回溯编程的范围和方法	R. J. Walker(1960), An enumerative technique for a class of combinatorial problems.
1965	S. Golamb 和 L. Baumert.的方案进行修改提出.Backtrack programming	Golomb, S. W., & Baumert, L. D. (1965). Backtrack programming. Journal of the ACM (JACM), 12(4), 516-524.
1976	Stallman, R. M., & Sussman, G. J. 提出相关性回溯法	Stallman, R. M., & Sussman, G. J. (1976). Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis.
1993	动态回溯法被提出	Ginsberg, M. L. (1993). Dynamic backtracking. journal of artificial intelligence research, 1, 25-46.

课后练习

37数独 1079活字印刷

算法

回溯算法

回溯算法是个思想，回溯法的实现方法有两种：递归和递推（也称迭代，非递归）。一般来说，一个问题两种方法都可以实现，只是在算法效率和设计复杂度上有区别。类比于图深度遍历的递归实现和非递归（递推）实现

https://blog.csdn.net/sinat_27908213/article/details/80599460?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task 对于回溯法来说，每次递归调用，很重要的一点是把每次递归的不同信息传递给递归调用的函数。而这里最重要的要传递给递归调用函数的信息，就是把上一步做过的选择排除，避免重复和无限递归。另外还有一个信息必须传递给递归函数，就是进行了每一步选择后，暂时还没构成完整的解，这个时候前面所有选择的汇总也要传递进去。而且一般情况下，都是能从传递给递归函数的参数处，得到结束条件的。

回溯算法是个思想，一般用递归实现，递归函数设计： 1、必须要有一个临时变量(初始时可以就直接传递一个字面量或者常量进去)传递不完整的解，表示截至当前解的情况，因为每一步选择后，暂时还没构成完整的解，这个时候这个选择的不完整解，也要想办法传递给递归函数。也就是，把每次递归的不同情况传递给递归调用的函数。【每一步的解的汇总信息传递下去】表示临时路径。 2、可以有一个全局变量，用来存储完整的每个解，一般是个集合容器（也不一定要有这样一个变量，因为每次符合结束条件，不完整解就是完整解了，直接打印即可）。【存储完整的解空间，也可以用类的属性】 3、最重要的一点，一定要在参数设计中，可以得到结束条件。一个选择是可以传递一个循环变量，也许是数组的长度，也许是数量，索引等等。【结束条件】 4、要保证递归函数返回后，状态可以恢复到递归前，以此达到真正回溯。【恢复状态：下一次递归前，把当前这一步的选择清除或者还原】回溯的意思就是要回去，递归函数自动保证了回去，但是我们设置的其他变量如果有必要的话也必须要回到原位。

通过循环变量或者临时路径进行扩展，看情况，一般循环变量扩展时增加1，临时路径扩展时尾部增加一步。做选择、扩展递归下一步、撤销选择。

两大类： 1，解空间树的深度或者路径长度已经明确告知为N，又分为子集树和排列树两种 2，解空间树的深度或者路径长度没有明确告知，求解后才知道

https://blog.csdn.net/weiyuefei/article/details/79316653 回溯法思路的简单描述是：把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：1. 使用约束函数，剪去不满足约束条件的路径；2.使用限界函数，剪去不能得到最优解的路径。问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。解空间树分为两种：子集树和排列树。两种在算法结构和思路上大体相同。

补充链接： https://www.jiqizhixin.com/graph/technologies/55e8bc82-9c28-4900-bf08-3f6f05a62d60 https://cs.lmu.edu/~ray/notes/backtracking/ https://www.quora.com/q/loveforprogramming/Backtracking-Memoization-Dynamic-Programming https://www.youtube.com/watch?v=gBC_Fd8EE8A

伪代码：

void findSolutions(n, other params) :
    if (found a solution) :
        solutionsFound = solutionsFound + 1;
        displaySolution();
        if (solutionsFound >= solutionTarget) : 
            System.exit(0);
        return

    for (val = first to last) :
        if (isValid(val, n)) :
            applyValue(val, n);
            findSolutions(n+1, other params);
            removeValue(val, n);

遍历所有从根节点到叶子节点的路径

   public List<List<Node>> rootToLeaf(Node root) {
        List<List<Node>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        LinkedList<Node> path = new LinkedList<>();
        dfs(root, result, path);
        return result;
    }
/*
*1，root为循环变量，不断发生变化，直到结束条件
*2，paths为最终解空间，不断丰富
*3，list为临时变量，表示当前汇总信息，传递下去
*/
    private void dfs(Node root, List<List<Node>> paths, LinkedList<Node> list) {
        if (root == null) return;
        list.add(root);
        if (root.left == null && root.right == null) {
            paths.add(new ArrayList<>(list));//一定要拷贝一份，因为后面list还要变
            list.removeLast();
            return;//到达叶子节点后，一定要返回；每次返回前要清除最后一个节点
        }
        dfs(root.left, paths, list);
        dfs(root.right, paths, list);
        list.removeLast();//4，恢复状态
    }

回溯法总结 0，leetcode的定义，与递归，深度优先搜索的关系 1，活结点，扩展节点，死节点 2，以0/1背包问题做例子 3，子集树，排列数 4，通用解法：路径，选择列表，做选择，撤销选择 5，leetcode例题 6，再回头看与递归，深度优先搜索的关系，外加与动态规划的关系 7，参考论文

mengxh1990 / WiseNetwork

可信认证 #2

回溯算法

基本描述

概念及原理

通用解法

leetcode例题

总结

回溯法

课后练习

算法

回溯算法