回溯算法小结

一. 回溯算法介绍

1.1 定义1.2 特征 二. 应用举例

2.1 Leetcode 46 全排列2.2 Leetcode 39 组合总和

回溯算法是指：用深度优先搜索对可行解进行暴力枚举，并在枚举后撤销当前操作，从而反复递归进行的搜索算法。

经过总结，回溯算法主要有如下特征：

尝试【新的变化】以该【新的变化】作为新的迭代入口进行迭代撤销【新的变化】重复以上过程 二. 应用举例 2.1 Leetcode 46 全排列

代码如下：

vector> permute(vector& nums) {
    vector> ans;
    backtracking(nums, ans, 0);
    return ans;
}
void backtracking(vector& nums, vector> ans, int pos) {
	// 递归出口（回溯法是递归，也要遵循递归的写法）
	if (pos = nums.size() - 1) {
		ans.push(nums); 
		return ;
	}
	// 递归条件
	backtrcking(nums, ans, pos + 1); // 不交换顺序，它本身也是一个解
	for (int i = pos + 1; i < nums.size(); ++i) { // 重复以下过程
		swap(nums[pos], nums[i]); // 尝试【新的变化】
		backtracking(nums, ans, i); // 以该【新的变化】作为新的迭代入口进行迭代
		swap(nus[pos], nums[i); // 撤销【新的变化】
	}
}

代码如下：

vector> combinationSum(vector& candidates, int target) {
    vector> ans;
    vector path;
    backtracking(candidates, target, path, ans, 0);
    return ans;
}
void backtracking(vector& candidates, int target, vector& path, vector>& ans, int pos) {
	// 不需要规定退出条件，因为下面的target > candidates[i]提前做了限制
	for (int i = pos; i < candidates.size(); ++i) { // 重复以下过程
		path.push_back(candidates[i]); // 尝试【新的变化】
		if (target == candidates[i]) {
			ans.push_back(path); // 以该【新的变化】作为新的迭代入口进
		}
		else if (target > candidates[i]) {
			backtracking(candidates, target - candidates[i], path, ans, pos);
		}
		path.pop_back(candidates[i]); // 撤销【新的变化】
	}
}