|
[code]package com.dam.combinationProblem.question1;
import java.util.*;
public class MySolution {
public static void main(String[] args) {
// int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};
int[] candidates = new int[]{10, -1, 2, -7, 6, 1, -5};
int target = 8;
/*int[] candidates = new int[]{2, 5, 2, 1, 0};
int target = 5;*/
MySolution solution = new MySolution();
List<LinkedList<Integer>> res = solution.combinationSum(candidates, target);
System.out.println("输出 => " + res);
}
public List<LinkedList<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
List<LinkedList<Integer>> result = new ArrayList<>();
if (len == 0) {
return result;
}
Arrays.sort(candidates);
System.out.println(Arrays.toString(candidates));
LinkedList<Integer> path = new LinkedList<>();
dfs(candidates, target, candidates.length, 0, path, result);
return result;
}
private void dfs(int[] candidates, int target, int length, int begin, LinkedList<Integer> path, List<LinkedList<Integer>> result) {
//当数组遍历完成,说明该节点已经拓展完成
if (begin == length) {
return;
}
//从begin开始,相当于前面的元素已经使用
for (int i = begin; i < length; i++) {
if (target - candidates[i] < 0) {
break;
}
if (i > begin && candidates[i] == candidates[i - 1]) {
continue;
}
path.addLast(candidates[i]);
//说明找到了解,无需往下拓展
if (target - candidates[i] == 0) {
//保存解
result.add((LinkedList<Integer>) path.clone());
path.removeLast();
return;
}
dfs(candidates, target - candidates[i], length, i + 1, path, result);
path.removeLast();
}
}
}
[/code] |
|