1. 原题链接
https://leetcode.com/problems/combination-sum-ii/description/
2. 题目要求
给定一个整型数组candidates[ ]和目标值target，找出数组中累加之后等于target的所有元素组合
注意：（1）每个可能的答案中，数组中的每一个元素只能使用一次；（2）数组存在重复元素；（3）数组中都是正整数；（4）不能存在重复解
3. 解题思路
这与第39题 Combination Sum 看起来很是类似，但一些细节要求完全不同，因此处理起来的方法也不相同。相同的是依旧采用递归的方法。
不存在重复解，但给定的数组中存在重复元素，因此先对candidates[ ]进行排序，方便处理重复元素的问题
4. 代码实现
1 import java.util.ArrayList; 2 import java.util.Arrays; 3 import java.util.List; 4 5 public class CombinationSum40 { 6 public static void main(String[] args) { 7 CombinationSum40 cs = new CombinationSum40(); 8 int[] candidates = {10, 1, 2, 7, 6, 1, 5}; 9 for (List l : cs.combinationSum2(candidates, 8)) 10 System.out.println(l); 11 } 12 13 public List<List<Integer>> combinationSum2(int[] candidates, int target) { 14 Arrays.sort(candidates); 15 for(int x:candidates) 16 System.out.print(x+" "); 17 System.out.println(); 18 List<List<Integer>> result = new ArrayList<List<Integer>>(); 19 combinationSum(result, new ArrayList<Integer>(), candidates, 0, target); 20 return result; 21 22 } 23 24 public void combinationSum(List<List<Integer>> result, List<Integer> tmp, int[] candidates, int start, int target) { 25 if (target > 0) { 26 for (int i = start; i < candidates.length; i++) { 27 if (i > start && candidates[i] == candidates[i - 1]) // 避免重复的结果 28 continue; // 结束for循环中其后的语句，跳回for循环 29 tmp.add(candidates[i]); 30 combinationSum(result, tmp, candidates, i + 1, target - candidates[i]); 31 tmp.remove(tmp.size() - 1); // 累加和超过target，则删去列表表尾元素 32 } 33 } 34 if (target == 0) { 35 result.add(new ArrayList<>(tmp)); 36 } 37 38 } 39 }