基本思想

回溯算法是一种递归算法，它试图通过尝试不同的选择，解决一个问题。它的基本思想是从可能的决策开始搜索，如果发现这条路往下走不能得到有效的解答，就返回上一层重新选择另外一种可能的决策，并且重复以上的步骤。

具体来说，回溯算法通过深度优先搜索的方式，遍历问题的解空间。在深度优先搜索的过程中，当搜索到某一层时，根据问题的限制条件判断该层的节点状态是否满足条件。如果条件不满足，则这个节点的状态被排除，并回溯到当前节点的父节点，重新进行遍历。如果条件满足，则继续搜索下一层的节点，并重复以上操作，直到搜索到一个符合条件的解或者遍历完整个解空间。

回溯算法一般适用于求解组合问题、排列问题、搜索问题等。由于在搜索过程中，需要不断地重新选择和放弃某个状态，所以回溯算法具有空间复杂度为 O(N) 的特点。

因为回溯算法的搜索路径呈现树形结构，所以有时候也被称作"回溯搜索"或"深度优先搜索+状态撤销"算法。

回溯算法的递归框架

回溯算法是一种典型的递归算法，它通常需要使用递归函数来实现。回溯算法的递归框架一般为以下形式：

def backtrack(candidate, state):if state == target:                        # 满足条件，输出结果output(candidate)return# 选择for choice in choices:make_choice(choice)                    # 做选择backtrack(candidate, state + 1)        # 递归进入下一层状态undo_choice(choice)                    # 撤销选择

这个递归框架通常包括三个部分：选择、递归和撤销选择。具体来说，每次迭代中，算法选择一个可用的状态或者变量，进行尝试。然后进入下一层状态，继续进行递归。如果递归过程中发现当前状态不符合要求，则需要撤销前面的选择，回到上一层状态，重新开始搜索。

在回溯算法中，重点是如何定义选择和撤销操作。这些操作通常和具体问题相关，需要根据问题的特点进行定义。回溯算法的实现应该包括以下步骤：

判断是否到达了目标状态。当搜索到符合要求的状态时，将其输出，并结束搜索。
选择当前状态或变量。在当前状态的所有可选序列、可选子节点等中，选择一个未被搜索过的状态或变量。
尝试选择新状态。在进入下一层状态之前，需要先尝试选择新状态，完成相应的操作，比如加入选择列表等。
递归进入下一层状态。进入下一层状态并继续搜索。
撤销选择。如果当前状态不符合要求，需要撤销前面所做的所有选择、完成的操作等，返回上一层状态，继续搜索其他可选序列或子节点。

组合问题

LeetCode第77题：https://leetcode.cn/problems/combinations/

首先定义两个全局变量用于存放结果集和当前候选集合：

// 存放所有满足条件的结果
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 当前得到的候选集
List<Integer> temp = new ArrayList<Integer>();

递归的终止条件：找到了一个子集大小为k的组合，即

if (temp.size() == k) {ans.add(new ArrayList<Integer>(temp));return;
}

选择

for(int i = cur; i<=n;i++){temp.add(i);	// 当前元素加入候选集合dfs(i+1,n,k);	// 递归进入下一层状态temp.remove(temp.size() - 1);	// 当前元素移除候选集合
}

完整代码

class Solution {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<Integer>();public List<List<Integer>> combine(int n, int k) {dfs(1, n, k);return ans;}public void dfs(int cur, int n, int k) {// 剪枝：可选的元素不足K个if (temp.size() + (n - cur + 1) < k) {return;}if (temp.size() == k) {ans.add(new ArrayList<Integer>(temp));return;}for(int i = cur; i<=n;i++){temp.add(i);dfs(i+1,n,k);temp.remove(temp.size() - 1);}}
}

组合总和

LeetCode 第39题：组合总和：https://leetcode.cn/problems/combination-sum/

首先定义两个全局变量用于存放结果集和当前候选集合：

// 存放所有满足条件的结果
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 当前得到的候选集
List<Integer> temp = new ArrayList<Integer>();

递归的终止条件：当前候选集合总和大于target或找到总和为target的组合，即

if(sum > target){return;
}
if(sum == target){res.add(new ArrayList<Integer>(temp));return;
}

选择

for(int i=index;i<candidates.length;i++){temp.add(candidates[i]);	// 当前元素加入候选集合sum+=candidates[i];			// 当前候选集总和dfs(candidates, target, i);	// 递归进入下一层状态// 当前元素移除候选集合sum -= temp.get(temp.size()-1);temp.remove(temp.size()-1);
}

完整代码

class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<Integer>();int sum = 0;public List<List<Integer>> combinationSum(int[] candidates, int target) {dfs(candidates, target, 0);return res;}public void dfs(int[] candidates, int target, int index){if(sum > target){return;}if(sum == target){res.add(new ArrayList<Integer>(temp));return;}for(int i=index;i<candidates.length;i++){temp.add(candidates[i]);sum+=candidates[i];dfs(candidates, target, i);sum -= temp.get(temp.size()-1);temp.remove(temp.size()-1);}}
}

组合去重

LeetCode第40题：组合总和 II：https://leetcode.cn/problems/combination-sum-ii/

在上一题组合求和基础上，定义一个used数组记录元素是否是否过：

递归的终止条件：当前候选集合总和大于target或找到总和为target的组合，即

if(sum > target){return;
}
if(sum == target){res.add(new ArrayList<Integer>(temp));return;
}

选择

for(int i=cur;i<candidates.length;i++){//当前元素是否有效if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false){continue;}temp.add(candidates[i]);	// 当前元素加入候选集合used[i] = true;		// 标记当前元素已使用sum += candidates[i];		// 当前候选集总和dfs(candidates,target,i+1,sum,used);		// 递归进入下一层状态// 当前元素移除候选集合sum -= temp.get(temp.size() - 1);temp.remove(temp.size() - 1);used[i] = false;
}
for(int i=index;i<candidates.length;i++){temp.add(candidates[i]);	// 当前元素加入候选集合sum+=candidates[i];			// 当前候选集总和dfs(candidates, target, i);	// 递归进入下一层状态// 当前元素移除候选集合sum -= temp.get(temp.size()-1);temp.remove(temp.size()-1);
}

完整代码

class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<Integer>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);boolean[] used = new boolean[candidates.length];dfs(candidates, target, 0, 0, used);return res;}public void dfs(int[] candidates, int target, int cur, int sum, boolean[] used){if(sum > target){return;}if(sum == target){res.add(new ArrayList<Integer>(temp));return;}for(int i=cur;i<candidates.length;i++){if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false){continue;}temp.add(candidates[i]);used[i] = true;sum += candidates[i];dfs(candidates,target,i+1,sum,used);sum -= temp.get(temp.size() - 1);temp.remove(temp.size() - 1);used[i] = false;}}
}

子集

子集: https://leetcode.cn/problems/subsets/

class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();Deque<Integer> temp = new ArrayDeque<Integer>();public List<List<Integer>> subsets(int[] nums) {dfs(nums, 0);return res;}public void dfs(int[] nums, int index){res.add(new ArrayList<Integer>(temp));for(int i=index;i<nums.length;i++){temp.addLast(nums[i]);dfs(nums, i+1);temp.removeLast();}}
}

全排列

全排列: https://leetcode.cn/problems/permutations/

class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<Integer>();public List<List<Integer>> permute(int[] nums) {boolean[] used = new boolean[nums.length];dfs(nums, used, 0);return res;}public void dfs(int[] nums, boolean[] used, int index){if(temp.size() == nums.length){res.add(new ArrayList<Integer>(temp));return;}for(int i=0;i<nums.length;i++){if(used[i]){continue;}used[i] = true;temp.add(nums[i]);dfs(nums, used, i+1);used[i] = false;temp.remove(temp.size()-1);}}
}