java数据结构与算法刷题-----LeetCode40. 组合总和 II_java实现leetcode40

作者：繁依Fanyi0 | 2024-07-20 08:52:19

踩

java实现leetcode40

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：`https://blog.csdn.net/grd_java/article/details/123063846`

文章目录

- 1. 实现方式1：典型回溯
- 2. 实现方式2：模拟树的深度优先遍历

解题思路

39题衍生题，39题基础上，加了一个条件，candidates数组中每个数字在同一个组合中只能使用一次。这些数字是有可能相同的。
这道题的难点在于，[1,7,1,6]为例，[1,1,6],[1,7],[7,1]都满足target = 8的条件，但是返回结果中不能同时返回[1,7]和[7,1]因为这两个组合是同一个，是重复的。
所以我们先将数组排序为[1,1,6,7]，当我们某个位置枚举时，如果和上次一样就跳过

例如，我们第一个位置先选用[1,1,6,7]标黄的1，枚举出[1,1,6],[1,7]，此时这个1就毕业了，它会腾出第一个位置
不跳过的情况下：我们第一个位置会直接用第二个位置的1，从而枚举出[1,7]. 此时就会枚举出两个相同的组合[1,7]和[1,7]
但是，现在我们，要切换下一个值来当前位置时。先比较下一个值是否和当前值一样，如果一样就跳过。从而不再次枚举[1,7]。
我们发现1 = 1,所以我们跳过这个1.然后继续判断比较后面的值6，发现不一样，那么下次就用6在第一个位置枚举

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/856023