关键词：
回溯法
回溯
1. 什么是回溯?
回溯法也叫回溯搜索法,是一种搜索的方式
2. 回溯法解决的问题
- 组合问题: N个数里面按一定规则找出k个数的集合
- 切割问题: 一个字符串按一定规则有几种切割方式
- 子集问题: 一个N个数的集合里有多少符合条件的子集
- 排列问题: N个数按一定规则全排列,有几种排列方式
- 棋盘问题: N皇后,解数独等等
组合是不强调元素顺序,排列强调元素顺序
例如: 1,2和2,1在组合上,是一个集合。
对排列来说, 1,2和2,1就是两个集合了
3. 回溯法的模板
-
回溯函数模板返回值以及参数
返回值一般为void，参数一开始不能一次性确定，所以一般先写逻辑，然后需要什么参数，就填充什么参数
void backtrack(参数) -
回溯函数终止条件
一般来说搜到叶子节点，即找到满足条件的一条答案，就把答案存放起来，并结束本层递归。
if (终止条件) 存放结果; return; -
回溯搜索的遍历过程
回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成树的深度
for(选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) 处理节点; backtrack(路径,选择列表); // 递归 回溯,撤销处理结果for循环就是遍历集合区间,可以理解一个节点有多少孩子,for循环就执行多少次。
（for循环横向遍历，backtrack纵向遍历）
综合，回溯算法模板如下：
void backtrack(参数)
if (终止条件)
存放结果;
return;
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）)
处理节点;
backtrack(路径，选择列表); // 递归
回溯，撤销处理结果
LeetCode题目列表
组合问题
77. 组合
/**
* 思路: 回溯法
* n相当于树的宽度, k相当于树的高度
* 1. 递归函数的返回值以及参数
* 定义两个全局变量, 一个是存放符合条件的单一结果, 一个用来存放符合条件结果的集合
* 函数一定要有n和k,还需要有一个参数为int类型的startIndex,用于记录本层递归中,集合从哪里开始遍历
*
* 2. 回溯函数终止条件
* path数组大小等于k的时候,保存起来,结束本层递归
*
* 3. 单层搜索的过程
* for循环每次从startIndex开始
*/
/*List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k)
if(n <= 0 || k <= 0)
return res;
List<Integer> path = new ArrayList<>();
backtrack(n, k, 1);
return res;
private void backtrack(int n, int k, int start)
if(path.size() == k)
res.add(new ArrayList<>(path));
return;
for (int i = start; i <= n; i++)
path.add(i);
backtrack(n, k, i+1);
path.remove(path.size()-1);
*/
// 剪枝优化
// 遍历的范围是可以优化的,比如n=4,k=4时,第一层for循环开始,从2开始就没有意义了。第二层for循环,从3开始就没有意义了
// 因此每层for循环最多到达 n - (k - path.size()) + 1
// n - 还需要选择的元素大小 + 1
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k)
if(n <= 0 || k <= 0)
return res;
List<Integer> path = new ArrayList<>();
backtrack(n, k, 1);
return res;
private void backtrack(int n, int k, int start)
if(path.size() == k)
res.add(new ArrayList<>(path));
return;
for (int i = start; i <= n - (k - path.size()) + 1; i++)
path.add(i);
backtrack(n, k, i+1);
path.remove(path.size()-1);
216 组合总和III
/**
* 思路: 回溯法
* 1. 递归函数的返回值以及参数
* 定义两个全局变量, 一个是存放符合条件的单一结果, 一个用来存放符合条件结果的集合
* 函数一定要有targetSum和k,还需要有一个参数为int类型的startIndex,用于记录本层递归中,集合从哪里开始遍历
* targetSum表示减去当前选择的元素后, 还需要多少目标和
*
* 2. 回溯函数终止条件
* path数组大小等于k并且targetSum == 0时,保存起来,结束本层递归
*
* 3. 单层搜索的过程
* for循环每次从startIndex开始
*/
/*List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n)
if(k <= 0)
return res;
backtrack(n, k, 1);
return res;
private void backtrack(int targetSum,int k, int startIndex)
if(targetSum < 0)
return;
if(targetSum == 0 && k == path.size())
res.add(new ArrayList<>(path));
return;
for (int i = startIndex; i <= 9; i++)
path.add(i);
targetSum -= i;
backtrack(targetSum,k, i+1);
targetSum += i;
path.remove(path.size()-1);
*/
// 剪枝优化
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n)
if(k <= 0)
return res;
backtrack(n, k, 1);
return res;
private void backtrack(int targetSum,int k, int startIndex)
// 剪枝优化
if(targetSum < 0)
return;
if(targetSum == 0)
if(k == path.size())
res.add(new ArrayList<>(path));
// 可能出现不满大小为k的路径, 虽然满足targetSum == 0,但是依然提前返回
return;
// 剪枝优化
// 范围优化: 9 - (k - path.size()) + 1
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++)
path.add(i);
backtrack(targetSum - i,k, i+1);
path.remove(path.size()-1);
17. 电话号码的字母组合
/**
* 思路: 回溯法
* 1. 构建一个数组对应字母与数字之间的映射关系
*
* 2. 递归函数的返回值以及参数
* 定义两个全局变量, 一个是存放符合条件的单一结果, 一个用来存放符合条件结果的集合
*
* 函数参数(String digits, int startIndex)
* digits: 每层选择列表
* startIndex: 记录本层递归中, 当前遍历到了哪一个数字
*
* 3. 回溯函数终止条件
* path大小等于digits大小, 保存到结果集, 结束本层递归
*
* 4. 递归函数每层for循环,从0开始遍历到每个数字映射的字符串的大小
*/
List<String> res = new ArrayList<>();
StringBuilder path = new StringBuilder();
String[] letterMap = new String[]"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz";
public List<String> letterCombinations(String digits)
if(digits == null || digits.length() == 0)
return res;
backtrack(digits, 0);
return res;
private void backtrack(String digits, int startIndex)
if(path.length() == digits.length())
res.add(new String(path.toString()));
return;
// 比如digits = "23", startIndex = 0对应字符'2', 则第一层遍历从0开始遍历到第一个字符的'2'的字符串"abc"大小为3
String letters = letterMap[digits.charAt(startIndex) - '0'];
for (int i = 0; i < letters.length(); i++)
// 选择元素
// "abc".charAt(0) = 'a'
char c = letters.charAt(i);
path.append(c);
// 递归进入下一层 startIndex + 1 对应字符'3'
backtrack(digits, startIndex + 1);
path.deleteCharAt(path.length()-1);
39. 组合总和
// 选择列表中元素无重复,但是可以重复选
/**
* 思路: 回溯
* 1. 递归函数的返回值以及参数
* 定义两个全局变量, 一个是存放符合条件的单一结果, 一个用来存放符合条件结果的集合
*
* 函数一个是选择列表, 一个startIndex, 一个是targetSum
* startIndex用于记录本层递归中,集合从哪里开始遍历, 由于可以重复选择元素, 所以下一层递归应该还是从当前元素的下标开始
*
* 2. 回溯函数终止条件
* targetSum == 0时,保存起来,结束本层递归
*
* 3. 单层搜索的过程
* for循环每次从startIndex开始
*/
/*List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target)
Arrays.sort(candidates);
backtrack(candidates,0, target);
return res;
private void backtrack(int[] candidates, int startIndex, int targetSum)
if(targetSum < 0)
return;
if(targetSum == 0)
res.add(new ArrayList<>(path));
return;
for (int i = startIndex; i < candidates.length; i++)
path.add(candidates[i]);
backtrack(candidates, i, targetSum - candidates[i]);
path.remove(path.size()-1);
*/
// 剪枝优化
// 排序 + 遍历范围优化
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target)
Arrays.sort(candidates);
backtrack(candidates,0, target);
return res;
private void backtrack(int[] candidates, int startIndex, int targetSum)
if(targetSum < 0)
return;
if(targetSum == 0)
res.add(new ArrayList<>(path));
return;
for (int i = startIndex; i < candidates.length && targetSum - candidates[i] >= 0; i++)
path.add(candidates[i]);
backtrack(candidates, i, targetSum - candidates[i]);
path.remove(path.size()-1);
40. 组合总和II
/**
* 思路: 回溯 + 剪枝优化(排序、遍历过程)
*
* 先对数组进行排序
*
* 1. 递归函数的返回值以及参数
* 定义两个全局变量, 一个是存放符合条件的单一结果, 一个用来存放符合条件结果的集合
*
* backtrack(int[] candidates, int startIndex, int targetSum, boolean[] visited)
* candidates: 选择列表
* startIndex: 用于记录本层递归中,集合从哪里开始遍历
* targetSum: 目标和
* visited: 访问数组,判断同层节点是否已经遍历过
*
* 2. 回溯函数终止条件
* targetSum < 0时, 不符合条件, 提前返回
* targetSum == 0时,保存起来,结束本层递归
*
* 3. 单层搜索的过程
* for循环每次从startIndex开始, 因为是排序数组,所以如果遍历到i时, targetSum已经小于0,则后面就不用再遍历了
*
*/
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target)
if(candidates == null || candidates.length == 0 || target == 0)
return res;
// 访问数组,判断同层节点是否已经遍历过
boolean[] visited = new boolean[candidates.length];
Arrays.sort(candidates);
backtrack(candidates, 0, target, visited);
return res;
private void backtrack(int[] candidates, int startIndex, int targetSum, boolean[] visited)
if(targetSum < 0)
return;
if(targetSum == 0)
res.add(new ArrayList<>(path));
return;
for (int i = startIndex; i < candidates.length && targetSum - candidates[i] >= 0; i++)
// 同一树层有两个重复的元素,不可以重复被选取
if(i > 0 && candidates[i] == candidates[i-1] && !visited[i-1])
continue;
// 同一树枝有两个重复的元素,但visited[i-1]为true,可以重复选取
path.add(candidates[i]);
visited[i] = true;
backtrack(candidates, i+1, targetSum-candidates[i], visited);
visited[i] = false;
path.remove(path.size()-1);
分割问题
131. 分割回文串
/**
* 思路: 回溯
*
* 1. 递归函数的返回值以及参数
* 定义两个全局变量, 一个是存放符合条件的单一结果, 一个用来存放符合条件结果的集合
*
* backtrack(String s, int startIndex)
* s: 选择列表
* startIndex: 用于记录本层递归中,集合从哪里开始遍历
*
* 2. 回溯函数终止条件
* targetSum == s.length() 时,保存起来,结束本层递归
*
* 3. 单层搜索的过程
* for循环每次从startIndex开始,如果满足回文子串的条件,则进入下一层递归
*
*/
List<List<String>> res = new ArrayList<>();
List<String> path = new ArrayList<>();
public List<List<String>> partition(String s)
backtrack(s, 0);
return res;
private void backtrack(String s, int startIndex)
if(startIndex == s.length())
res.add(new ArrayList<>(path));
return;
for (int i = startIndex; i < s.length(); i++)
String substring = s.substring(startIndex, i + 1);
// 是回文子串
if(isPalindrome(substring))
path.add(substring);
backtrack(s, i+1);
path.remove(path.size()-1);
// 判断是否是回文串
private boolean isPalindrome(String substring)
int left = 0;
int right = substring.length()-1;
while(left < right)
if(substring.charAt(left) == substring.charAt(right))
left++;
right--;
else
break;
return left >= right;
93. 复原IP地址
/**
* 思路: 回溯
*
* 1. 递归函数的返回值以及参数
* 定义两个全局变量, 一个是存放符合条件的单一结果, 一个用来存放符合条件结果的集合
*
* backtrack(String s, int startIndex, int dotNum)
* s: 选择列表
* startIndex: 用于记录本层递归中,集合从哪里开始遍历
* dotNum: 句点的数量
*
* 2. 回溯函数终止条件
* dotNum == 3时, 做进一步判断
* (要注意第四段的下标是否越界)
* 如果第四段子串是合法的,则将第四段添加到路径中,最后添加到结果集res中,添加完毕后还要进行一步回溯操作,剔除刚刚添加的第4段
*
* 3. 单层搜索的过程
* for循环每次从startIndex开始,如果子串是合法的,则进入下一层递归
* 若不合法,则提前结束本层循环
*
*/
List<String> res = new ArrayList<>();
StringBuilder path = new StringBuilder();
public List<String> restoreIpAddresses(String s)
if(s == null || s.length() == 0)
return res;
// 超过12个数字无法组成IP地址
if(s.length() > 12)
return res;
backtrack(s, 0, 0);
return res;
private void backtrack(String s, int startIndex, int dotNum)
// 当出现 0.10.0.时, 即出现3个'.'时, 就进入判断
if(dotNum == 3)
// 判断第四段子字符串是否合法,合法就放入res中
// 要注意第四段子字符串下标是否已经超过s字符串的大小！！！！
if(startIndex < s.length() && isValid(s.substring(startIndex, s.length())))
// 满足则添加最后一段,然后添加到结果集中
res.add(path.append(s.substring(startIndex, s.length())).toString());
// 添加完0.10.0.10后, 要记得回溯, 即删除最后的"10", 回退到只有3段的时候, 即0.10.0.
String[] split = path.toString().split("\\\\.");
// path的长度 - 最后"10"的长度 得到"10"的起始位置
path查看详情
算法----01背包问题和完全背包问题leetcode系列问题题解(代码片段)
背包问题1、01背包入门1.1二维背包1.2一维背包2、01背包问题2.1背包装最多问题416.分割等和子集1049.最后一块石头的重量II2.2凑满背包方法数问题494.目标和2.3双重维度问题474.一和零3、完全背包问题3.1凑满组合问题518.零钱兑换II3.2... 查看详情
算法----01背包问题和完全背包问题leetcode系列问题题解(代码片段)
背包问题1、01背包入门1.1二维背包1.2一维背包2、01背包问题2.1背包装最多问题416.分割等和子集1049.最后一块石头的重量II2.2凑满背包方法数问题494.目标和2.3双重维度问题474.一和零3、完全背包问题3.1凑满组合问题518.零钱兑换II3.2... 查看详情
一篇文零基础带你搞懂回溯（万字：核心思维+图解+习题+题解思路+代码注释）(代码片段)
...回溯思想和本质的分析二、配套练习：1、组合类问题leetcode77.组合leetcode216.组合总和IIIleetcode39.组合总和leetcode40.组合总和IIleetcode17.电话号码的字母组合2、分割字符串类leetcode131.分割回文串leetcode93.复原IP地址3、集合子集问... 查看详情
一篇文零基础带你搞懂回溯（万字：核心思维+图解+习题+题解思路+代码注释）(代码片段)
...回溯思想和本质的分析二、配套练习：1、组合类问题leetcode77.组合leetcode216.组合总和IIIleetcode39.组合总和leetcode40.组合总和IIleetcode17.电话号码的字母组合2、分割字符串类leetcode131.分割回文串leetcode93.复原IP地址3、集合子集问... 查看详情
初识“回溯算法”讲解及leetcode对应例题解析(代码片段)
初识“回溯算法”讲解及LeetCode对应例题解析回溯算法1、回溯算法的概念2、回溯算法的一般解题思路3、解决问题的方法例题一：二叉树中和为某一值的路径（1）题目描述（2）题目分析（3）代码实现... 查看详情
初识“回溯算法”讲解及leetcode对应例题解析(代码片段)
初识“回溯算法”讲解及LeetCode对应例题解析回溯算法1、回溯算法的概念2、回溯算法的一般解题思路3、解决问题的方法例题一：二叉树中和为某一值的路径（1）题目描述（2）题目分析（3）代码实现... 查看详情
一文通数据结构与算法之——回溯算法+常见题型与解题策略+leetcode经典题(代码片段)
...素的子集个数2.2.3递增子序列2.3组合问题[77.组合](https://leetcode-cn.com/problems/co 查看详情
算法系列之回溯算法ivleetcode51.n皇后和leetcode37.解数独(代码片段)
51.N皇后力扣题目链接按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数n，返... 查看详情
leetcode通关：连刷十四题，回溯算法完全攻略(代码片段)
刷题路线：https://github.com/youngyangyang04/leetcode-master大家好，我是被算法题虐到泪流满面的老三，只能靠发发文章给自己打气！这一节，我们来看看回溯算法。回溯算法理论基础什么是回溯在二叉树的路径问题里... 查看详情
算法----01背包问题和完全背包问题leetcode系列问题题解(代码片段)
背包问题1、01背包入门1.1二维背包1.2一维背包2、01背包问题2.1背包装最多问题416.分割等和子集1049.最后一块石头的重量II2.2凑满背包方法数问题494.目标和2.3双重维度问题474.一和零3、完全背包问题3.1凑满组合问题518.零钱兑换II3.2... 查看详情
leetcode-46.全排列--回溯算法--python(代码片段)
全排列问题使用回溯算法解决思路：定义res列表存放最后的结果定义track列表构建排列存放每次的排列在backtrack函数中，for循环中1.满足条件，加入res，2.做选择：track.append(nums[i])3.回溯函数：backtrack(nums,trac... 查看详情
leetcode46permutationspython实现（回溯算法）(代码片段)
Givenacollectionofdistinctintegers,returnallpossiblepermutations.Example:Input:[1,2,3]Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]回溯算法自己的一个思路如下：需要保留数字使用情况，my_nums增加和删除元素等操作1classSolu 查看详情
leetcode回溯算法#07子集问题i+ii，巩固解题模板并详解回溯算法中的去重问题(代码片段)
子集力扣题目链接给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。示例1：输入：nums=[1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示... 查看详情
[回溯算法]leetcode40.组合总和ii(c实现)(代码片段)
题目代码/***Returnanarrayofarraysofsize*returnSize.*Thesizesofthearraysarereturnedas*returnColumnSizesarray.*Note:Bothreturnedarrayand*columnSizesarraymustbemalloced,assumecallercallsfree().*/int*path;int 查看详情
leetcode——分割回文串(代码片段)
1.题目2.题解类似全排列问题，回溯算法解决startIndex为切割起点，i为切割终点直接回溯三部曲：递归函数返回值——一般是void，backTraking()确定终止条件，startIndex>=s.length()，代表切割到最后一位单层... 查看详情
leetcode题解——算法思想之排序(代码片段)
快速选择堆1.KthElement桶排序1.出现频率最多的k个元素2.按照字符出现次数对字符串排序荷兰国旗问题1.按颜色进行排序快速选择用于求解KthElement问题，也就是第K个元素的问题。可以使用快速排序的partition()进行实现。需要先打乱... 查看详情
leetcode----打家劫舍系列问题思路与题解(代码片段)
打家劫舍198.打家劫舍213.打家劫舍II337.打家劫舍III树形dp递归+记忆化总结198.打家劫舍/***思路:动态规划*1.确定dp数组以及下标含义*dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额dp[i]**2.确定递推公式*dp[i]=Math.max(dp[i-1],... 查看详情