组合总和 II

40。组合总和 II

难度：中等

主题：数组，回溯

给定一组候选数字（candidates）和一个目标数字（target），找到候选数字中候选数字总和达到目标的所有唯一组合。

候选中的每个数字在组合中只能使用一次。

注意：解决方案集不得包含重复的组合。

示例1：

• 输入： 候选人 = [10,1,2,7,6,1,5]，目标 = 8
• 输出： [[1,1,6], [1,2,5], [1,7], [2,6]]

示例2：

• 输入： 候选人 = [2,5,2,1,2]，目标 = 5
• 输出： [[1,2,2], [5]]

约束：

• 1
• 1
• 1

解决方案：

我们可以使用回溯方法。关键思想是首先对数组进行排序以轻松处理重复项，然后使用回溯探索所有可能的组合。

让我们用 PHP 实现这个解决方案：40。组合和 II

解释：

1. 排序：对候选数组进行排序，以轻松处理重复项并确保组合按排序顺序形成。
2. 回溯：回溯函数用于探索所有可能的组合。
   • 如果目标变为零，我们将当前组合添加到结果中。
   • 我们从当前索引开始迭代候选者。如果候选与前一个相同，我们会跳过它以避免重复组合。
   • 我们从目标中减去当前候选，并使用新目标和下一个索引递归调用回溯函数。
   • 递归调用将继续，直到我们找到有效的组合或穷尽所有可能性。
3. 剪枝：如果候选者超过了目标，我们会提前跳出循环，因为更多候选者也将超过目标。

此代码将输出总和达到目标的所有唯一组合，同时确保每个候选在每个组合中仅使用一次。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是组合总和 II的详细内容。更多信息请关注PHP中文网其他相关文章！