回溯其实大部分都是采用递归的写法，通过dfs尝试所有的可能性，获取自己想要的结果；本质上可以构造成一棵树，构造节点时如果条件不符合则意味着可以进行剪枝（即跳过此次逻辑）
目前刷到的题主要有这么几类：排列，组合，切割子串，子集。
我个人一般使用的常规模板是
private void dfs(){
//退出条件
if(符合条件){
添加到结果并return或者return true;
}
//有些时候是没有循环的
for(本层节点所有情况){
//剪枝
if(不满足条件){
continue;
}
将当前选择添加到节点，如list.add(i);arr[x][y]='Q';之类的结果操作
dfs(总结果，子结果，下一种情况)
将当前选择从子结果中移除，一般都是list.remove(list.size()-1)，部分情况有StringBuilder,sb.deleteCharAt(sb.length()-1)
//假如没有循环，那么就应该还有dfs，如果有循环，下次dfs是下个循环的事，这里就不需要有
dfs(其他可能)//比如如果是选择，那就是不选当前方案；如果是坐标，那就是上下左右四种情况
}
}
算法题一般都要求结果不能有重复项，起码是不能有完全相同的重复项，因此去重是必然存在的，比如[1,1,2]，不管是排列还是组合[1,2]和[1,2]虽然是两个不同位置的1，但是由于结果一样，因此必须去重，一般对于这种去重都是用hashset在当层循环去重校验。
部分场景会对原始数组进行排序，这样子在去重或者比较时候，可以更好的进行剪枝条件的处理，有些返回结果也会依赖这个排序。比如组合，因为顺序没有意义，[1,2]和[2,1]又是同一种概念，因次可以通过整体排序，然后下次进入dfs之后，直接从下一种情况开始。
还有一个要求一般都是当前选过的不能再选了，比如普通的排列组合，路径，数独问题，因此一般都会通过额外的数据结果来进行标识，一般可能是个flag数组。但是也有一些特殊情况允许重复使用，比如39. 组合总和
切割子串的题就遇到两个，切割回文串和复原ip，其核心思想和排列组合差不多，不过排列组合是当前这位选不选，切割问题都是当前这位切不切，这种问题一般需要考虑好切割边界，是左闭右开，还是左闭右闭；
子集问题一般都是讲符合条件的子级添加到结果，但是子级比较复杂的是重复问题，比如[1,1,2]情况[1,2]和[1,2]、[2,1]都是重复的，但是[1,1,2]又是满足条件的，因此不能单纯的整体添加到hash表，只能通过往后剪枝避免这种情况，然后每层单独使用hash过滤
比较难的几个：数独、红皇后、格雷编码，大部分都是判断条件比较复杂，其核心还是回溯的模板。最难的#332 重新安排行程则是图论里的，只能先记住遍历顶点-删边-添加顶点这种操作。
后面可以慢慢刷题：题单 - 力扣（LeetCode）全球极客挚爱的技术成长平台
算法
组合总和（不允许重复使用）
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
dfs(result, new ArrayList<>(), candidates, target,0);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> list, int[] candidates, int target,int index) {
if (target == 0) {
result.add(new ArrayList<>(list));
return;
}
//注意，i从index开始是为了避免重复;
//以[2,3,6,7]为例,[2,2,3],[2,3,2],[3,2,2]其实都是相同的结果,
//2,2,3表示的是选择第一个，第一个，第二个，表示为(112),当固定前两种选择的时候，该字数会尝试所有可能的情况,比如111,113,114；因此当第二个数字为3时，可理解为12x，由于已经尝试过112，因此无需再尝试比当前位靠前的情况
//必须有一个结构可以记录当前层级所有的情况，且不会透传到下层
HashSet<Integer> set=new HashSet<>();
for (int i = index; i < candidates.length; i++) {
int temp = candidates[i];
// 由于已经排序，当该元素大于target，则后续值都没有比较的意义了
if (temp > target) {
return;
}
if(set.contains(temp)){
continue;
}else{
set.add(temp);
}
list.add(temp);
dfs(result, list, candidates, target - temp,i+1);
list.remove(list.size() - 1);
}
}
全排列2
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] color=new boolean[nums.length];
dfs(result, new ArrayList<>(), nums,color);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> list, int[] nums,boolean[] color) {
if (list.size() == nums.length) {
result.add(new ArrayList<>(list));
return;
}
HashSet<Integer> set=new HashSet<>();
for (int i = 0; i < nums.length; i++) {
//选过了
if(color[i]){
continue;
}
//同轮次中已经处理过这种情况了
if(set.contains(nums[i])){
continue;
}else{
set.add(nums[i]);
}
list.add(nums[i]);
color[i]=true;
dfs(result, list, nums,color);
list.remove(list.size() - 1);
color[i]=false;
}
}
切割-复原ip地址
输入：s = “25525511135” 输出：[“255.255.11.135”,“255.255.111.35”]
public List<String> restoreIpAddresses(String s) {
int step = s.length() / 4;
List<String> result = new ArrayList<>();
// 如果长度小于4
if (step == 0) {
return result;
}
dfs(result, new ArrayList<>(), s, 0);
return result;
}
private void dfs(List<String> result, List<String> list, String s, int start) {
if (list.size() == 3) {
if (isVaild(s, start, s.length())) {
StringBuilder sb = new StringBuilder();
for (String str : list) {
sb.append(str);
sb.append(".");
}
sb.append(s.substring(start));
result.add(sb.toString());
}
return;
}
for (int i = start; i < s.length(); i++) {
if (!isVaild(s, start, i + 1)) {
continue;
}
list.add(s.substring(start, i + 1));
dfs(result, list, s, i + 1);
list.remove(list.size() - 1);
}
}
private boolean isVaild(String str, int left, int right) {
if (left >= right) {
return false;
}
if (str.charAt(left) == '0' && right-left>1) {
return false;
}
if (right - left > 3) {
return false;
}
Integer value = Integer.valueOf(str.substring(left, right));
return value >= 0 && value <= 255;
}
子集2
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的
子集
（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
public List<List<Integer>> subsetsWithDup(int[] nums) {
//排序是针对的向后剪枝方案的去重
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
dfs(result, new ArrayList<>(), nums, 0);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> list, int[] nums, int start) {
result.add(new ArrayList<>(list));
if (start == nums.length) {
return;
}
HashSet<Integer> set=new HashSet<>();
//排序需要color数组，因为存在顺序，所以不能单纯的往后剪枝
//子集和组合都可以根据往后剪枝来处理
//set永远是保证单轮次不重复处理
for (int i = start; i < nums.length; i++) {
if(set.contains(nums[i])){
continue;
}else{
set.add(nums[i]);
}
list.add(nums[i]);
dfs(result, list, nums, i + 1);
list.remove(list.size() - 1);
}
}