回溯type
status
date
slug
summary
tags
category
icon
password
Property
回溯算法（Backtracking）：一种能避免不必要搜索的穷举式的搜索算法。采用试错的思想，在搜索尝试过程中寻找问题的解，当探索到某一时，发现原先的选择并不满足求解条件，或者还需要满足更多求解条件时，就退回一步（回溯）重新选择，这种走不通就退回再走的技术称为「回溯法」，而满足回溯条件的某个状态的点称为「回溯点」。
简单来说，回溯算法采用了一种 「走不通就回退」 的算法思想。
回溯算法通常用简单的递归方法来实现，在进行回溯过程中更可能会出现两种情况：
- 找到一个可能存在的正确答案
- 在尝试了所有可能的分布方法之后宣布该问题没有答案
以求解
[1, 2, 3]的全排列为例
按顺序枚举每一位上可能出现的数字，之前已经出现的数字在接下来要选择的数字中不能再次出现。对于每一位，进行如下几步：
- 选择元素：从可选元素列表中选择一个之前没有出现过的元素
- 递归搜索：从选择的元素出发，一层层地递归搜索剩下位数，直到遇到边界条件时，不再向下搜索
- 撤销选择：一层层地撤销之前选择的元素，转而进行另一个分支的搜索。直到完全遍历完所有可能的路径
从全排列的决策树中可以看出：
- 每一层中有一个或多个不同的节点，这些节点以及节点所连接的分支代表了「不同的选择」
- 每一个节点代表了求解全排列问题的一个「状态」，这些状态是通过「不同的值」来表现的
- 每向下递推一层就是在「可选元素列表」中选择一个「元素」加入到「当前状态」
- 当一个决策分支探索完成之后，会逐层向上进行回溯
- 每向上回溯一层，就是把所选择的「元素」从「当前状态」中移除，回退到没有选择该元素时的状态（重置状态），从而进行其他分支的探索
写回溯算法
- 画出递归树，找到状态变量(回溯函数的参数)
- 根据题意，确立结束条件
- 找准选择列表(与函数参数相关)
- 判断是否需要剪枝
- 作出选择，递归调用，进入下一层
- 撤销选择
子集
题目：给你一个整数数组
nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集，可以按任意顺序返回解集。示例：
- 递归树
选择列表里的数，都是选择路径(红色框)后面的数，比如[1]这条路径，他后面的选择列表只有 "2、3"，[2] 这条路径后面只有 "3" 这个选择，那么这个时候，就应该使用一个参数
start，来标识当前的选择列表的起始位置。也就是标识每一层的状态，因此被形象的称为 "状态变量"，最终函数签名如下- 找结束条件
所有路径都应该加入结果集，所以不存在结束条件。或者说当
start参数越过数组边界的时候，程序就自己跳过下一层递归了，因此不需要手写结束条件，直接加入结果集- 找选择列表
子集问题的选择列表，是上一条选择路径之后的数，即
- 判断是否需要剪枝
从递归树中看到，路径没有重复的，也没有不符合条件的，所以不需要剪枝
- 做出选择(即for 循环里面的)
- 撤销选择
子集 II
题目：给一个整数数组
nums ，其中可能包含重复元素，请返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。示例：
组合总和
题目：给一个无重复元素的整数数组
candidates 和一个目标整数target ，找出candidates中可以使数字和为目标数 target 的所有不同组合 ，并以列表形式返回。可以按任意顺序返回这些组合。candidates中的同一个数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为 target 的不同组合数少于 150 个。示例：
组合总和II
题目：给定一个候选人编号的集合
candidates和一个目标数target ，找出 candidates中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次 。注意：解集不能包含重复的组合。示例：
全排列
题目：给定一个不含重复数字的数组
nums，返回其所有可能的全排列，可以按任意顺序返回答案。示例：
全排列 II
题目：给定一个可包含重复数字的序列
nums，按任意顺序返回所有不重复的全排列。示例：
单词搜索
题目：给定一个
m x n二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true ；否则，返回false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例：
复原 IP 地址
题目：有效 IP 地址 正好由四个整数（每个整数位于
0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。给定一个只包含数字的字符串
s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在s中插入 '.' 来形成。不能重新排序或删除s中的任何数字。可以按任何顺序返回答案。示例：
字符串的排列
题目：输入一个字符串，打印出该字符串中字符的所有排列。可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例：
括号生成
题目：数字
n代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且有效的括号组合。示例：
解数独
题目：编写一个程序，通过填充空格来解决数独问题。数独的解法需遵循如下规则：
- 数字
1-9在每一行只能出现一次
- 数字
1-9在每一列只能出现一次
- 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次
数独部分空格内已填入了数字，空白格用
'.' 表示。示例：
因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！那么会直接返回， 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！
判断棋盘是否合法有如下三个维度：
- 同行是否重复
- 同列是否重复
- 9宫格里是否重复
24 点游戏
题目：给定一个长度为4的整数数组
cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。你须遵守以下规则:
- 除法运算符
'/'表示实数除法，而不是整数除法，4 /(1 - 2 / 3)= 4 /(1 / 3)= 12。
- 每个运算都在两个数字之间。特别是，不能使用
“-”作为一元运算符。例如，如果cards =[1,1,1,1]，则表达式“-1 -1 -1 -1”是 不允许 的。
- 你不能把数字串在一起，如果
cards =[1,2,1,2]，则表达式“12 + 12”无效。
如果可以得到这样的表达式，其计算结果为
24 ，则返回 true ，否则返回 false 。示例：