回溯算法学习
- 回溯实际上是一个有一些枝被剪掉了的决策树的遍历过程。
- 1、路径：也就是已经做出的选择。
- 2、选择列表：也就是你当前可以做的选择。
- 3、结束条件：也就是到达决策树底层，无法再做选择的条件
result = []
void backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return;
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」。
撤销选择–>回溯！
本题代码
结束条件：
target==0,说明目前ans中存在正确结果,ans数组存入res结果集中。
选择列表：即为for循环的范围，为了去重，利用st使得后面的元素的选择列表中不包括前面被选过的元素。
去重：以[2,2,3] [3,2,2]为例，既然[2,2,3]可以，这个组合在以2为第一层结点的时候就会被发现，3的选择列表中只有[3,6,7].
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> ans;
part(candidates,ans,target,0);
return res;
}
void part(vector<int>& candidates,vector<int>& ans,int target,int st)
{
if(target==0)
{
res.push_back(ans);
}
else
{
for(int i=st;i<candidates.size();i++)
{
if(candidates[i]>target)
continue;
ans.push_back(candidates[i]);
part(candidates,ans,target-candidates[i],i);
ans.pop_back();
}
}
}
};