组合总和 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