- 全局变量：保存结果
- 参数：递归函数的参数选择，通常是两种参数。
- 状态变量： result需要保存的值
- 条件变量： 判断搜索是否完毕以及搜索是否合法
- 完成条件： 完成条件是决定状态变量和条件变量取何值时可以判断整个搜索流程结束。整个搜索流程结束有两个含义：搜索成功并保存结果何搜索失败并返回上一次状态。
- 递归过程： 传递当前状态给下一次递归进行搜索。
let res = []; //存储结果
function backtrack(path, condition, ...) {
if (judge(condition)) { // 满足条件
res.push(path);
return;
}
for (let select of selectList) {
if (剪枝条件) break;
path.push(select); // 走某条路
backtrack(path, newSelectList);
path.pop(); // 返回上一个十字路口
}
}- 排列，组合
- 数组，字符串，给定一个特定的规则，尝试找到某个解
- 二维数组下的DFS搜索
我筛选了leetCode中hot和面试常考题库中关于回溯的题目，题目由易到难，覆盖每个使用场景。
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
/**
* 1. 定义res数组存储结果
* 2. 每个子集为状态变量，集合的元素个数为条件变量
* 3. 子集的元素数量小于等于集合的元素数量为限制条件，满足条件时添加到结果数组，否则回退到上一步
* 4. 下一层搜索的集合需要去掉已添加到状态变量中的元素
*/
var subsets = function(nums) {
let res = [];
let n = nums.length;
function back(path, i) {
if (i <= n) {
res.push(path.slice(0));
}
for (let j = i; j < n; j++) {
path.push(nums[j]);
back(path, j + 1);
path.pop();
}
}
back([], 0);
return res;
};/**
* @param {number[]} nums
* @return {number[][]}
* 直接遍历，遇到一个数就把所有子集加上该数组成新的子集，遍历完毕即是所有子集
*/
var subsets = function(nums) {
var res = [[]];
for (var i = 0; i < nums.length; ++i) {
var length = res.length;
for (var j = 0; j < length; ++j) {
res.push([...res[j], nums[i]]);
}
}
return res;
};给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
var array = [];
var path = [];
dfs(nums, path, array);
return array;
};
var dfs = function(nums, path, array) {
if (path.length === nums.length) {
array.push(path.slice());
} else {
for (var i = 0; i < nums.length; ++i) {
if (path.indexOf(nums[i]) === -1) { // 这里的判断很精髓
path.push(nums[i]);
dfs(nums, path, array);
path.pop(nums[i]);
}
}
}
};给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
示例 1：
输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
candidates = candidates.sort((x, y) => x - y);
var array = [];
find(candidates, target, array, [], 0);
return array;
};
var find = function(candidates, target, array, path, idx) {
if (target === 0) {
array.push(path.slice());
} else {
for (var i = idx; i < candidates.length && candidates[i] <= target; ++i) {
path.push(candidates[i]);
find(candidates, target - candidates[i], array, path, i);
path.pop();
}
}
};给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function(s) {
};给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
};给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效 IP 地址。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
};