一、回溯算法介绍

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
下面以一道leetcode题目为例讲解一下回溯算法的计算过程以及回溯算法解题的主要步骤。
下面以一道leetcode题目来进行回溯算法的算法题解以及代码实现，题目描述如下

既然要选择最大的一个可行序列，那么我们就尽可能地把大的数字放在高位上（这也是贪心算法的思想），如果这个高位放不下我们选的大数字，那么就退而求其次，把我们选的大数字撤下去，换上一个稍微小点的试试。
下面给出演示，以n=5为例，首先准备一个空数组 [0,0,0,0,0,0,0,0,0] 用于存放结果，在最高位放5得到 [5,0,0,0,0,5,0,0,0] ，这样最高的位置就安排好了，第二位如果放4显然是不满足“距离为i”的条件的，因此，我们把4换下来，放上3，得到 [5,3,0,0,3,5,0,0,0] 以此类推，这个挨个尝试的枚举算法就被成为回溯算法。下面给出这道题的代码实现

public class Solution {
    public int[] constructDistancedSequence(int n) {
        //记录结果的数组
        int[] result = new int[2 * n - 1];
        //记录哪些数字用过了
        boolean[] used = new boolean[n];
        canPutIn(result, used, 0);
        return result;
    }

    //判断当前位置放置这一个数字是否合适
    public boolean canPutIn(int[] result, boolean[] used, int index) {
        //可以安防的最大数字
        int n = used.length;
        while (n > 0 && used[n - 1]) n--;
        //数字都安放好了就返回true
        if (n == 0) return true;
        
        //可以安放的最大位置，index的设置是为了减少循环的时间
        for (int i = index; i < result.length; i++) {
            if(result[i] == 0){
                index = i;
                //如果无处安放，返回false（前提是n > 1）
                if(index + n >= result.length && n > 1)
                    return false;
                break;
            }
        }

        while (n > 0) {
        	//因为1和其他数字是要区别对待的，因此这里使用ifelse区分一下
            if (n == 1) {
                if (result[index] == 0 && !used[n - 1])
                {
                	//把当前的尝试数字放进去
                    used[n - 1] = true;
                    result[index] = n;
                    //如果可行，返回true
                    if (canPutIn(result, used, index + 1)) return true;
                    //如果不可行，撤下来，while循环会用n--的方式再换个数字
                    result[index] = 0;
                    used[n - 1] = false;
                }
            } else {
                if (result[index] == 0 && result[index + n] == 0 && !used[n - 1]) {
                    result[index] = n;
                    result[index + n] = n;
                    used[n - 1] = true;
                    if (canPutIn(result, used, index + 1)) return true;
                    result[index] = 0;
                    result[index + n] = 0;
                    used[n - 1] = false;
                }
            }
            n--;
        }
        return false;
    }
}

从代码中可以看出，回溯算法有这样几个步骤

1. 设置结果集用于存储结果
2. 尝试向结果集里面放入一个值，挨个尝试通常用循环来实现
3. 再上一步放入了值的基础上，接着往结果中放值，直到填满结果集，返回。这一步通常是使用递归来实现的
4. 如果放入的值不能够满足条件，把放上的值退回来
5. 如果所有的尝试都不行，那就指定是不行了

概括起来将，回溯算法会经历 设置结果集、循环试结果、递归深层试、不行就回退、最后回结果 五个步骤，代码上分别对应了建立变量、循环语句、递归函数、变量复原和循环外返回结果五个过程，掌握了具体的结构之后回溯还是很容易解的。