干货分享|图解两种常见回溯解法
发布网友
发布时间：2024-10-23 22:32
共1个回答
热心网友
时间：2024-11-01 12:44
基础写法以力扣题库中的 78.子集 为例。题目要求找到给定数组的所有子集，且数组元素互不相同。回溯题通常有以下两种模板写法。
解法一：先添加再回溯。在递归调用前将当前子集添加到结果列表中，递归后再移除最后添加的元素，以回溯至上一层。
解法二：先回溯后添加。不将当前子集添加至结果列表，直接递归，递归结束后将当前元素加入子集，再回溯至上一层。
两种解法实质相同，主要差异在于添加子集与回溯的时机。解法一在每次遍历时添加子集，解法二则在递归结束后添加。
图示帮助理解两种解法差异，加深的集合表示最终结果的数组集合。解法一与解法二的 index 定义相似，但作用不同，用于后续待选择数组的左边界，解法二用 index 判断加入结果集的边界条件。
不同的题目适用不同解法，或需对解法进行调整。下面总结经典回溯题目的要素。
题目一：78.子集，元素互不相同，数组的所有子集。
*条件：考虑数组的最后一个数。
选择不可重复，数组元素不相同。
题目二：90.子集II，元素可能相同，所有不重复子集。
*条件：考虑数组的最后一个数。
选择不可重复，数组元素可能相同。
题目三：77.组合，确定数组（1- n）的 k 个数集合。
*条件：当前已选择元素的个数为 k。
选择不可重复，数组元素不相同。
题目四：39.组合总和，元素互不相同，找出和为 target 的组合。
*条件：考虑数组的最后一个数或当前已选择元素和为 target。
选择可重复，数组元素不相同。
题目五：40.组合总和 II，元素可能相同，找出和为 target 的组合。
*条件：考虑数组的最后一个数或当前已选择元素和为 target。
选择不可重复，数组元素可能相同。
题目六：216.组合总和III，确定数组（1- 9）找出和为 target 的 k 个数的组合。
*条件：当前已选择元素。
总结，40.组合总和II 和 90.子集II 需考虑重复生成子集，整体解法相似。组合总和中的特殊情况允许重复选择元素，通过调整调用函数时传入的 index 解决。
其余题目常规，关键确定加入集合的条件。
处理重复操作，当集合有重复元素时，需避免结果重复。解法一在 for 循环内加入判断条件，解法二通过引入布尔变量选择是否重复。
两种解法均能解决此类问题，解法一简洁，解法二稍复杂。
总结回溯算法的两种常见写法和进阶去重方法。根据不同题目要求和*，选择合适的解法。
本文旨在加深对回溯算法的理解，灵活运用基本方法和技巧。
