回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。因为回溯的本质是穷举，换句话说就是暴力解法，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
回溯法，一般可以解决如下几种问题：
组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等
回溯搜索的遍历过程通常是一个N叉树的结构：
回溯算法模板框架如下：
回溯方法用backtracking名字表示，方法都是用void返回，然后定义终止条件，最后进行收集结果。掌握这个模版，我们所做的各种回溯算法题都离不开这个模版。
void backtracking(参数) {
if (终止条件) {
收集结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
添加组合;
backtracking(路径，选择列表); // 递归，参数修改成下一层级状态
回溯操作：撤销处理结果，回到上层分支
}
}
各题题解:
//解法参考自：https://www.bilibili.com/video/BV1854y1m7WR/?spm_id_from=333.337.search-card.all.click&vd_source=40c24e77b23dc2e50de2b7c87c6fed59
// ###### [组合总和](https://leetcode.cn/problems/combination-sum/)
/**
* dfs的 return条件是 target == 0，找到条件也是 target == 0
*/
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates); //先排序，用于可以剪枝操作
dfs(candidates, target, 0);
return result;
}
/**
* 深度优先回溯算法
* @param candidates 候选集合
* @param target 剩余需要组合的值
* @param start 在候选集合中的位置
*/
public void dfs(int[] candidates, int target, int start) {
if (target == 0) {
//找到这个组合，当组合放入结果，然后结束这个层级往下
result.add(new ArrayList<>(path));
return;
}
//没有找到，则继续从当前候选序列里面取出，候选序列的起始为candidates的idx下标
for (int i=start;i<candidates.length;i++) {
//剪枝操作：如果当前canditates[i]大于target了，则这个分支的选取都结束了
if (candidates[i] > target) {
break;
}
//先试着把当前数放入组合
path.add(candidates[i]);
//继续从i开始选数，因为数可以取重复的;然后转移状态，tagert要为减去candidates[i]的新值；继续dfs往下一层搜索
dfs(candidates, target-candidates[i], i);
path.remove(path.size()-1); //回溯：删除最新添加的数，走for循环的下一个i，即走并行的下一个分支
}
}
}
// ###### [子集](https://leetcode.cn/problems/subsets/)
/**
* dfs的 return条件是 找的序号等于了数组长度，找到条件是 只要添加了新元素就是新的结果
*/
class Solution1 {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
result.add(new ArrayList<>()); //空集也是子集
dfs(nums, 0);
return result;
}
public void dfs(int[] nums, int start) {
if (start >= nums.length) {
return;
}
for (int i=start;i<nums.length;i++) {
path.add(nums[i]);
//在子集里，只要path组合新增了，就是一个新的子集，就需要添加到result里面去
result.add(new ArrayList<>(path));
dfs(nums, i+1); //往下层走，i需要+1，因为不能元素不能重复
path.remove(path.size()-1); //回溯回到上层分支
}
}
}
// ###### [全排列](https://leetcode.cn/problems/permutations/)
/**
* dfs的 return条件是 path.size == nums.leng，即所有元素都找完一遍了；找到条件也是 path.size == nums.leng
*/
class Solution2 {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
dfs(nums);
return result;
}
public void dfs(int[] nums) {
if (path.size() == nums.length) { //结束条件是 搜索长度满了，该全排列结束
result.add(new ArrayList<>(path));
return;
}
for (int i=0;i<nums.length;i++) {
//去重
if (path.contains(nums[i])) {
continue;
}
path.add(nums[i]);
dfs(nums);
path.remove(path.size()-1);
}
}
}
