回溯法的本质是一种通过暴力穷举来解决问题的算法。它通过逐步构建可能的候选解，并在确定当前步骤已经无法得到有效解时，撤销（回溯） 上一步或几步的操作，再尝试其他的可能性

回溯法的通用模板是：

1. 判断是否是边界条件
2.for循环下：
  2.1 做选则
  2.2 递归
  2.3 撤销选择

有时回溯法和多级遍历题目类似，是否选择用回溯法，主要看一个点：要不要回退。不需要回退，就可以不使用回溯法

看以下题目：

【leetcode44.全排列】

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

解法如下：

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> now = new ArrayList<>();
    boolean[] contains = new boolean[nums.length];
    return backTrace(nums, result, contains, now);
}

public List<List<Integer>> backTrace(int[] nums, List<List<Integer>> result, boolean[] contains, List<Integer> now) {
    // 边界条件
    if (now.size() == nums.length) {
        result.add(new ArrayList<>(now));
        return result;
    }
    for (int i = 0; i < nums.length; i++) {
        // 做选择
        if (!contains[i]) {
            now.add(nums[i]);
            contains[i] = true;
            // 递归
            backTrace(nums, result, contains, now);
            // 撤销选择
            contains[i] = false;
            now.remove(now.size() - 1);
        }
    }
    return result;
}

要点：

1、将result和now不断向下传递，用于向里塞值

2、边界条件时，以now构造新的list，防止引用冲突

3、做选择时，需要注意通过boolean[]判重

4、撤销条件时，需要同时撤销now元素添加和boolean[]判重记录

【leetcode22. 括号生成】

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

public List<String> generateParenthesis(int n) {
    int left = n;
    int right = n;
    int dis = 0;
    List<String> result = new ArrayList<>();
    StringBuilder sb = new StringBuilder();

    genNext(left, right, dis, sb, result);
    return result;

}

private void genNext(int left, int right, int dis, StringBuilder sb, List<String> result) {
    // 边界
    if (left == 0 && right == 0) {
        result.add(String.valueOf(sb));
    }
    // 选择
    if (dis == 0) {
        sb.append("(");
        left -= 1;
        dis += 1;
        genNext(left, right, dis, sb, result);
        left += 1;
        dis -= 1;
        sb.deleteCharAt(sb.length() - 1);
    } else {
        if (left > 0) {
            sb.append("(");
            left -= 1;
            dis += 1;
            genNext(left, right, dis, sb, result);
            left += 1;
            dis -= 1;
            sb.deleteCharAt(sb.length() - 1);
        }
        if (right > 0) {
            sb.append(")");
            right -= 1;
            dis -= 1;
            genNext(left, right, dis, sb, result);
            right += 1;
            dis += 1;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

回溯法的模板：边界、（条件）选择、回撤，这个题条件分成dis == 0即只能加左括号和dis > 0，可以加右括号或者左括号，实际上是三种

每一种做完了都要记得回撤

可以加左，可以加右，这种场景应该是顺序执行，而不应该是if-else，因为if-else就是二选一了，而回溯则是一路走到底，然后回退到上游再执行下一种，只要有回撤流程，就一定不会出错

另：回溯法千万不要用return参数的方法，一定要用一个list去承接结果，在边界时把结果存到list里面，还要注意创建新对象，避免引用问题