理论基础
-
回溯法（回溯搜索法）
- 回溯函数就是递归函数
- 本质是穷举
- 解决的问题
- 组合问题（不强调元素顺序，需去重）
- 切割问题
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题（强调元素顺序）
- 棋盘问题：N皇后
-
回溯法模板（可抽象为树形结构——N叉树 来解决问题）
- 递归返回值以及参数（一般为void）
- 终止条件
- 回溯搜索的遍历过程
void backtracking(参数){ if(终止条件){ 存放结果; return; } for(选择:本层集合中元素(树中结点孩子的数量就是集合的大小)) { 处理节点; backtracking(路径，选择列表);//递归 回溯，撤销处理结果 } }
77.组合
class Solution {
public List<List<Integer>> result =new ArrayList<>();//二维
public List<Integer> path=new LinkedList<>();//一维
public List<List<Integer>> combine(int n, int k) {
backtracking(n,k,1);
return result;
}
void backtracking(int n ,int k,int startIndex)//n为传入的集合大小
{
if(path.size()==k)//终止条件：树形结构的叶子节点
{
result.add(new ArrayList<>(path));
return;
}
//单层搜索递归逻辑
for(int i=startIndex;i<=n;i++)
{
path.add(i);
backtracking(n,k,i+1);
int size=path.size();
path.remove(size-1);
}
}
}
减枝操作
class Solution {
public List<List<Integer>> result =new ArrayList<>();//二维
public List<Integer> path=new LinkedList<>();//一维
public List<List<Integer>> combine(int n, int k) {
backtracking(n,k,1);
return result;
}
void backtracking(int n ,int k,int startIndex)//n为传入的集合大小
{
if(path.size()==k)//终止条件：树形结构的叶子节点
{
result.add(new ArrayList<>(path));
return;
}
//单层搜索递归逻辑
//至多从哪开始
for(int i=startIndex;i<=n-(k-path.size())+1;i++)
{
path.add(i);
backtracking(n,k,i+1);
int size=path.size();
path.remove(size-1);
}
}
}
216. 组合总和 III
class Solution {
public List<List<Integer>> result =new ArrayList<>();//二维
public List<Integer> path=new LinkedList<>();//一维
public List<List<Integer>> combinationSum3(int k, int n) {
backtracking(9,k,1,n);
return result;
}
void backtracking(int n ,int k,int startIndex,int Sum)//n为传入的集合大小
{
int sum=0;
for(int i=0;i<path.size();i++)
{
sum+=path.get(i);
}
if(sum==Sum&&path.size()==k)//终止条件：树形结构的叶子节点
{
result.add(new ArrayList<>(path));
return;
}
//单层搜索递归逻辑
for(int i=startIndex;i<=n;i++)
{
path.add(i);
backtracking(n,k,i+1,Sum);
int size=path.size();
path.remove(size-1);
}
}
}
剪枝
class Solution {
public List<List<Integer>> result =new ArrayList<>();//二维
public List<Integer> path=new LinkedList<>();//一维
public List<List<Integer>> combinationSum3(int k, int n) {
backtracking(9,k,1,n);
return result;
}
void backtracking(int n ,int k,int startIndex,int Sum)//n为传入的集合大小
{
int sum=0;
for(int i=0;i<path.size();i++)
{
sum+=path.get(i);
}
if(sum>Sum) return;//剪枝
if(sum==Sum&&path.size()==k)//终止条件：树形结构的叶子节点
{
result.add(new ArrayList<>(path));
return;
}
//单层搜索递归逻辑
for(int i=startIndex;i<=n-(k-path.size())+1;i++)
{
path.add(i);
backtracking(n,k,i+1,Sum);
int size=path.size();
path.remove(size-1);
}
}
}
17. 电话号码的字母组合
class Solution {
StringBuilder path=new StringBuilder();
List<String> result=new ArrayList<>();
String[] letterMap={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
if(digits==null|| digits.length()==0)
return result;
//映射
//树的深度取决于digits里数字的个数
//树的宽度取决于数字对应的字符串长度
backtracking(digits,0);
return result;
}
void backtracking(String digits,int Index)
{
if(Index==digits.length())
{
result.add(path.toString());
return ;
}
int digit=(digits.charAt(Index)-'0');
String letter=letterMap[digit];
for(int i=0;i<letter.length();i++)
{
path.append(letter.charAt(i));
backtracking(digits,Index+1);
path.deleteCharAt(path.length()-1);
}
}
}