LeetCode:40. Combination Sum II(Medium)

1. 原题链接

https://leetcode.com/problems/combination-sum-ii/description/

2. 题目要求

给定一个整型数组candidates[ ]和目标值target,找出数组中累加之后等于target的所有元素组合

注意:(1)每个可能的答案中,数组中的每一个元素只能使用一次;(2)数组存在重复元素;(3)数组中都是正整数;(4)不能存在重复解

3. 解题思路

这与第39题 Combination Sum 看起来很是类似,但一些细节要求完全不同,因此处理起来的方法也不相同。相同的是依旧采用递归的方法。

不存在重复解,但给定的数组中存在重复元素,因此先对candidates[ ]进行排序,方便处理重复元素的问题

4. 代码实现

 import java.util.ArrayList;
import java.util.Arrays;
import java.util.List; public class CombinationSum40 {
public static void main(String[] args) {
CombinationSum40 cs = new CombinationSum40();
int[] candidates = {10, 1, 2, 7, 6, 1, 5};
for (List l : cs.combinationSum2(candidates, 8))
System.out.println(l);
} public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
for(int x:candidates)
System.out.print(x+" ");
System.out.println();
List<List<Integer>> result = new ArrayList<List<Integer>>();
combinationSum(result, new ArrayList<Integer>(), candidates, 0, target);
return result; } public void combinationSum(List<List<Integer>> result, List<Integer> tmp, int[] candidates, int start, int target) {
if (target > 0) {
for (int i = start; i < candidates.length; i++) {
if (i > start && candidates[i] == candidates[i - 1]) // 避免重复的结果
continue; // 结束for循环中其后的语句,跳回for循环
tmp.add(candidates[i]);
combinationSum(result, tmp, candidates, i + 1, target - candidates[i]);
tmp.remove(tmp.size() - 1); // 累加和超过target,则删去列表表尾元素
}
}
if (target == 0) {
result.add(new ArrayList<>(tmp));
} }
}
上一篇:php gd:图片无法显示,因为其中包含错误


下一篇:【树】Path Sum II(递归)