题目描述:
给定一个数组 candidates和一个目标数 target,找出 candidates中所有可以使数字和为 target的组合。
candidates中的每个数字在每个组合中只能使用一次。
说明:
- 所有数字(包括目标数)都是正整数。
- 解集不能包含重复的组合。
示例1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
示例2:
输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]
题目难度:中等
分析:
这一题和上一题唯一的区别就是数组中的元素不可以重复使用,解题的思路是先排序,然后穷举,同时利用Set去重即可。
代码如下:
class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { // 用Set来去重 Set<List<Integer>> res = new HashSet<>(); List<Integer> list = new ArrayList<>(); // 排序过的元素才可以去重 Arrays.sort(candidates); if (candidates.length == 0) { return new ArrayList<>(); } combinationSumHelp(res, list, candidates, target, 0); return new ArrayList<>(res); } /** * @param res 结果集 * @param list 结果集中的集合 * @param candidates 数组 * @param target 目标数 * @param start 开始递归的下标 */ private void combinationSumHelp(Set<List<Integer>> res, List<Integer> list, int[] candidates, int target, int start) { if (target == 0) { List<Integer> temp = new ArrayList<>(list); res.add(temp); } else if (target > 0) { for (int i = start; i < candidates.length; i++) { list.add(candidates[i]); combinationSumHelp(res, list, candidates, target - candidates[i], i + 1); list.remove(list.size() - 1); } } } }
总结:
可以使用Set进行去重。递归要注意结束条件,否则会死循环。