回溯算法

      回溯算法实际上一个类似枚举的深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回（也就是递归返回），尝试别的路径。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。回溯法说白了就是穷举法。回溯法一般用递归来解决。

回溯法一般都用在要给出多个可以实现最终条件的解的最终形式。回溯法要求对解要添加一些约束条件。总的来说，如果要解决一个回溯法的问题，通常要确定三个元素：

1、选择。对于每个特定的解，肯定是由一步步构建而来的，而每一步怎么构建，肯定都是有限个选择，要怎么选择，这个要知道；同时，在编程时候要定下，优先或合法的每一步选择的顺序，一般是通过多个if或者for循环来排列。

2、条件。对于每个特定的解的某一步，他必然要符合某个解要求符合的条件，如果不符合条件，就要回溯，其实回溯也就是递归调用的返回。
3、结束。当到达一个特定结束条件时候，就认为这个一步步构建的解是符合要求的解了。把解存下来或者打印出来。对于这一步来说，有时候也可以另外写一个issolution函数来进行判断。注意，当到达第三步后，有时候还需要构建一个数据结构，把符合要求的解存起来，便于当得到所有解后，把解空间输出来。这个数据结构必须是全局的，作为参数之一传递给递归函数。

给出一道例题 leetcode78题 子集

题目描述：

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。

本题可以采用遍历的方式解决。遍历的方式比较好理解，就是拿到一个数以后，除了把原来的子集备份一份，还要把所有的子集都增加当前的数，得到新的子集

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<Integer>());
        
        for(int num : nums){
            int length = result.size();
            for(int i = 0; i < length; i++){
                List<Integer> temp = new ArrayList<>(result.get(i));
                temp.add(num);
                result.add(temp);
            }
        }
        
        return result;
    }
}

       在这里重点说一下回溯的算法。回溯算法的基本形式是“递归+循环”。正因为循环中嵌套着递归，递归中包含循环，这才使得回溯比一般的递归和单纯的循环更难理解，其实我们熟悉了它的基本形式，就会觉得这样的算法难度也不是很大。原数组中的每个元素有两种状态：存在和不存在。

① 外层循环逐一往临时集合 temp 中加入元素 nums[i]，使这个元素处于存在状态

② 开始递归，递归中携带加入新元素的 temp，并且下一次循环的起始是 j元素的下一个，因而递归中更新 j值为 j + 1

③ 将这个从中间集合 temp 中移除，使该元素处于不存在状态

回溯的过程比较难理解，可以断点调试一下下面的代码，看一下运行的过程，便于理解回溯的过程

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        
        sub(result, temp, nums, 0);
        
        return result;
    }
    private void sub(List<List<Integer>> result, List<Integer> temp, int[] nums, int i){
        result.add(new ArrayList<Integer>(temp));
        for(int j = i; j < nums.length; j++){
            temp.add(nums[j]);
            sub(result, temp, nums, j+1);
            temp.remove(temp.size()-1);
        }
    }
}