LeetCode 40.组合总和 II题意要点候选数组存在重复数字每个元素只能使用1次解集不能包含重复组合不能重复选取同一个位置元素但值可以相同要去重和39题区别39可重复选元素本题每个下标只能选一次并且要跳过同层重复数字Java完整代码排序回溯去重javaimport java.util.ArrayList;import java.util.Arrays;import java.util.List;class Solution {public ListList combinationSum2(int[] candidates, int target) {ListList result new ArrayList();List path new ArrayList();Arrays.sort(candidates); //排序方便跳过重复元素backtrack(candidates, target, 0, path, result);return result;}private void backtrack(int[] candidates, int remain, int start, ListInteger path, ListListInteger res) { if (remain 0) { res.add(new ArrayList(path)); return; } if (remain 0) return; for (int i start; i candidates.length; i) { //同层跳过重复数字避免产生重复组合 if (i start candidates[i] candidates[i - 1]) { continue; } int val candidates[i]; path.add(val); //i1下一层不能再选当前位置元素每个元素只用一次 backtrack(candidates, remain - val, i 1, path, res); path.remove(path.size() - 1); } }}核心关键点先排序把相同数字放到一起便于去重istart candidates[i]candidates[i-1] 同一递归层级跳过重复值只跳过同层深层可以继续选不同位置相同值递归起点是 i1 不能复用当前下标元素与39题i不同回溯加入元素递归后撤销选择测试样例javapublic static void main(String[] args) {Solution snew Solution();int[] nums{10,1,2,7,6,1,5};System.out.println(s.combinationSum2(nums,8));//[[1,1,6],[1,2,5],[1,7],[2,6]]}复杂度时间O(2^n)最坏所有组合都合法n为数组长度空间O(n)递归栈临时path如果你想要剪枝优化版本循环提前break我可以加上。