春困秋乏夏打盹，现在正是会经常打盹儿的时候，为了换换脑子振奋一下精神，默默打开了leetcode练练脑子。
一道组合总和瞪着大眼看了半天，用递归试了又试结果就是不对，无奈还是去Google一下吧，那能怎么办呢，谁让咱是小菜鸟呢
一看才知道这是用回溯解决啊，先看看维基百科对回溯法的解释吧：
回溯法是暴力搜索法的一种
对于某些计算问题而言，回溯法是一种可以找出所有（或一部分）解的一般性算法，尤其适用于约束满足问题（在解决约束满足问题时，我们逐步构造更多的候选解，并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解，转而测试其他的部分候选解）
回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确解答的时候，它将取消上一步甚至上几步的计算，再通过其他的可能的分步解答再次尝试寻找问题的答案。回溯法常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
- 找到一个可能存在的正确答案
- 在尝试了所有可能的分步方法后宣告该问题没有答案
小白理解：回溯法就是按照深度优先搜索，按一条路一直往下走，遇到正确解了就加入结果集，然后后退一步或几步继续查找其他解；如果发现不满足条件了，就后退一步或几步选另一条路往下走。
光看文字解释也整不太明白（反正我是这样的。。），实践才是真道理，看一下相关的题目吧。
1. 组合总和
问题描述：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
var combinationSum = function(candidates, target) {
var res = [];
candidates = candidates.sort((a, b) => a-b);
find(candidates, target, res, [], 0)
return res;
}
/**
* arr: 数组
* target：目标数
* res: 结果集
* path: 候选解
* j: for循环的起始下标
*/
function find (arr, target, res, path, j) {
var sum = getSum(path);
if (sum === target) { // 符合条件，加入结果集
res.push([...path]);
return;
}
if (sum > target) { // 大于目标值，直接返回
return;
}
// 下标从j开始，避免解集重复。比如arr是[2,3,6,7]，target是7，开始得到一个正解是[2,2,3]，当候选解第一个元素是3时，如果i还从0开始，就会得到[3,2,2], 使解集重复
for (var i = j; i < arr.length; i++) {
path.push(arr[i]);
find(arr, target, res, path, i);
// 无论是该路径大于target还是等于target，都需要对其删除最后一个元素，进行其余支路的搜索
path.pop();
}
}
function getSum(path) {
var sum = path.reduce((s, n) => {
return s += n;
}, 0)
return sum;
}
分析：
- 定义全局结果数组：var res = []
- 调用递归函数：find
- 返回结果集：res
- 定义递归函数
- 参数
- 终止条件：sum === target，把正解加入结果集中
- 剪枝条件：sum > target，过滤掉不正确的
- 回溯搜索下一结果：path.pop()，删除最后一个，进行其余支路的搜索
2. 组合总和II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
分析：
这道题跟上题的区别在于：
- 数组 candidates 里面的元素可以重复
- 数组中的每个元素在每个组合中只能使用一次
因为数组元素可以重复，就可能导致解集重复。比如candidates = [10,1,2,7,6,1,5]，target = 8；其中正解包括[1,7], [7,1], 这两个就是重复的，第一个解的1是candidates中的第二个元素，第二个解的1是candidates中的第6个元素。
针对这个问题，我们可以先对数组排序，这样相同元素位置紧邻。这样上面的两个正解就变成：[1,7],[1,7]；我们根据下面这个if条件：
if (i > j && arr[i] === arr[i - 1]) {
continue
}
过滤掉第二个相同的解。
针对第二个问题：每个元素在每个组合中只能使用一次。我们在进行递归的时候最后一个参数的传参为i + 1, 这样就解决了这个问题。
代码：
var combinationSum2 = function(candidates, target) {
var res = [];
candidates = candidates.sort((a,b) => a-b)
find(candidates, target, res, [], 0)
return res;
};
function find(arr,target, res, path, j) {
var sum = getSum(path);
if (sum === target) {
res.push([...path]);
return;
}
if (sum > target) {
return;
}
for (var i = j; i < arr.length; i++) {
if (i > j && arr[i] === arr[i - 1]) { // 保证解集不重复
continue
}
path.push(arr[i]);
find(arr,target, res, path, i + 1); // i + 1保证 每个数字在每个组合中只能使用一次。
path.pop();
}
}
function getSum (path) {
var sum = path.reduce((s, num) => {
s += num
return s
}, 0)
return sum;
}
3. 全排列
题目描述：
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
分析：
首先递归的终止条件是：path.length === nums.length，如果符合条件就加入结果集当中。
为了保证每个元素在候选解中只出现一次，我们用一个visited对象保存状态，记录某个元素是否使用过。
var permute = function(nums) {
const res = []
const path = []
range (nums, res, path, {})
return res;
};
function range (nums, res, path, visited) {
if (path.length === nums.length) {
res.push([...path])
return;
}
for(var i = 0; i < nums.length; i++) {
if (!visited[i]) {
visited[i] = true
path.push(nums[i])
range(nums, res, path, visited)
path.pop()
visited[i] = false
}
}
}
4. 全排列II
题目描述：
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
分析：
该题跟上一题的不同就是数组可包含重复数字，所以要在上一题的基础上去除重复排列。
首先把数组排序，然后添加如下判断：
if (visited[i] || (i > 0 && nums[i] === nums[i - 1] &&!visited[i - 1])) continue
在visited[i]的基础上添加了(i > 0 && nums[i] === nums[i - 1] &&!visited[i - 1])
如果不加这个条件，当数组是[1,1,2]时，正解包含两个[1,1,2], 一个下标是0 1 2的排列，一个下标是1 0 2的排列，由于数组前两个元素都是1，两种排列会导致一样的结果。我们加上面那个条件的作用是只保留下标顺序排列的一个解。
var permuteUnique = function(nums) {
const res = []
const path = []
nums.sort((a,b) => a-b)
range (nums, res, path, {})
return res;
};
function range (nums, res, path, visited) {
if (path.length === nums.length) {
res.push([...path])
return;
}
for(var i = 0; i < nums.length; i++) {
if (visited[i] || (i > 0 && nums[i] === nums[i - 1] &&!visited[i - 1])) continue
visited[i] = true
path.push(nums[i])
range(nums, res, path, visited)
path.pop()
visited[i] = false
}
}
5. 子集
题目描述：
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
这是求子集，所以每次递归的时候都把path加进结果集
var subsets = function(nums) {
var res = [];
var path = [];
find(nums, res, path, 0)
return res;
};
function find (nums, res, path, j) {
res.push([...path])
for (var i = j; i < nums.length; i++) {
path.push(nums[i])
find(nums, res, path, i + 1)
path.pop();
}
}
6. 子集II
题目描述：
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
分析：
该题比上一题多了一个条件：数组可能包含重复元素。
我们根据之前的经验，添加一个判断条件：
if (i > j && nums[i] === nums[i-1]) continue
只保留顺序添加的一个正解。
var subsetsWithDup = function(nums) {
var res = [];
var path = [];
nums.sort((a,b) => a-b)
find(nums, res, path, 0)
return res;
};
function find (nums, res, path, j) {
res.push([...path])
for (var i = j; i < nums.length; i++) {
if (i > j && nums[i] === nums[i-1]) continue
path.push(nums[i])
find(nums, res, path, i + 1)
path.pop();
}
}
经过上面几道题，回溯法的解题步骤一般是：
- 定义全局结果数组
- 调用递归函数
- 返回结果集
- 定义递归函数
- 确定参数
- 确定终止条件
- 剪枝条件
- 回溯搜索下一结果：path.pop()，删除最后一个，进行其余支路的搜索
当数组包含重复元素时，可以利用类似if (i > j && nums[i] === nums[i-1]) continue这种条件判断来去重
如有不恰当的地方，欢迎指正～～
