干货分享|图解两种常见回溯解法

发布网友 发布时间：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 循环内加入判断条件，解法二通过引入布尔变量选择是否重复。

两种解法均能解决此类问题，解法一简洁，解法二稍复杂。

总结回溯算法的两种常见写法和进阶去重方法。根据不同题目要求和*，选择合适的解法。

本文旨在加深对回溯算法的理解，灵活运用基本方法和技巧。