回溯 算法-爱代码爱编程
模版
// 主函数
main(
{
// 1: 定义返回的结果集合res
// 2: 定义回溯所需的组合combination,索引index
// 3: 调用回溯函数
backtrack(XXXX);
// 4: 结束 return
}
// 回溯函数
void backtrack(res, combination, index)
{
// 递归结束条件
if (满足题目要求的目标) {
res.push_back(combination)
return;
}
// 临时变量
new_idx = index;
new_combination = combination;
for (选择列表) { // 或者if
// 1: 做选择
//按需更新当前组合 new_combination
// 2:递归回溯
backtrack(res, new_commbination, new_index);
// 3: 撤销选择
// 恢复当前组合new_combination = combination
}
// 上述可能使用for遍历选择列表 或者使用 if更新
}
括号生存
https://leetcode.cn/problems/generate-parentheses/
电话号码的字母组合
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/