最近在leetcode上写了一些题，学习了回溯算法，这里和大家一起分享一下😊
回溯算法是一个尝试搜索的过程，有点像走迷宫？打个比方，当我们进入迷宫之后，我们会随意选择一条路，如果这时候有点小聪明的话，我们可以每拐入一个方向就在路口做记号，然后就这样走呀走呀走到尽头，结果是条死胡同，所以我们就会选择原路返回到做记号的最近一个路口，然后打叉叉❌，放弃这条路（剪枝），然后像这样继续尝试搜索，直到走出迷宫。
回溯就是这样，在尝试中寻找原问题的解，过程中一旦发现条件不符合，就回溯返回上一层。
首先看一下leetcode Q78（子集）：
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题要求子集，可以用回溯的思想去探索 --- 是不是可以用深度优先遍历那样的方法把我们的解集找出来 --- 走不通就退回，用下一条路，然后一个一个地加入最终结果中：
var subsets = function(nums) {
//最终结果存在res
var res = [];
//返回二维数组，temp用于存储每一个结果的数组形式
var temp = [];
//调用回溯方法
backtrack(res,nums,0,temp);
return res;
};
var backtrack = function(res,nums,index,temp){
//这里每次探索都是结果，所以res不用条件判断
res.push(temp.slice());
//对我们的nums进行探索，这里的i的起始点变化，是为了去重
for(let i = index; i < nums.length; i ++){
//往下探索的过程
temp.push(nums[i]);
backtrack(res,nums,i + 1,temp);
//回溯
temp.pop();
}
}
再看一个leetcode Q39(组合总和): 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这里做这道题，每次探索可以用target去减你选的那个数，若是探索下去target === 0，则这个探索过程是问题的解，若是target < 0，则舍弃这个解：
代码实现：
var combinationSum = function(candidates, target) {
var res = [];
var temp = [];
candidates = candidates.sort((a,b) => a - b);
//调用回溯算法
backtrack(candidates,target,res,0,temp);
return res;
};
var backtrack = function(candidates,target,res,index,temp){
//不合适的解
if(target < 0){
return;
}
//合适的解
if(target === 0){
res.push(temp.slice()); // push一个数组
return;
}
//每次探索都会将target值更新
for(let i = index; i < candidates.length; i ++){
if(target < 0){
break;
}
temp.push(candidates[i]);
backtrack(candidates,target - candidates[i],res,i,temp);
temp.pop();
}
}
实际上，我们画出来的图，是这些题的解空间，在这写范围内求解，而找到合适的正确的递归结束条件和每次探索的方式就可以尝试使用回溯算法，leetcode上有回溯算法的题集和题解，让我们理解和掌握回溯算法吧 :>
第一次发文，有什么建议或者我有什么写得不好的，望告知，蟹蟹~🦀🦀
