|
[code]package com.dam.combinationProblem.question2;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class MySolution {
public static void main(String[] args) {
int[] smallLengthArr = new int[]{3, 5, 1};
int[] needNum = new int[]{2, 2, 2};
int min = 4;
int max = 6;
MySolution solution = new MySolution();
List<LinkedList<Integer>> res = solution.combinationSum(smallLengthArr, needNum, min, max);
System.out.println("输出 => " + res);
}
public List<LinkedList<Integer>> combinationSum(int[] smallLengthArr, int[] needNum, int min, int max) {
//拓展数组
int arrLen = 0;
for (int i = 0; i < needNum.length; i++) {
arrLen += needNum[i];
}
//无须切割
int len = smallLengthArr.length;
List<LinkedList<Integer>> result = new ArrayList<>();
if (len == 0 || arrLen == 0) {
System.out.println("输出数据有问题");
return result;
}
Arrays.sort(smallLengthArr);
//最终数组
int[] lastSmallLengthArr = new int[arrLen];
int count = 0;
for (int i = 0; i < smallLengthArr.length; i++) {
for (int j = 0; j < needNum[i]; j++) {
lastSmallLengthArr[count++] = smallLengthArr[i];
}
}
System.out.println("处理之后的数组:" + Arrays.toString(lastSmallLengthArr));
LinkedList<Integer> path = new LinkedList<>();
dfs(lastSmallLengthArr, 0, min, max, 0, arrLen, path, result);
return result;
}
private void dfs(int[] lastSmallLengthArr, int value, int min, int max, int begin, int length, LinkedList<Integer> path, List<LinkedList<Integer>> result) {
//当数组遍历完成,说明该节点已经拓展完成
if (begin == length) {
return;
}
//从begin开始,相当于前面的元素已经使用
for (int i = begin; i < length; i++) {
if (value + lastSmallLengthArr[i] > max) {
break;
}
if (i > begin && lastSmallLengthArr[i] == lastSmallLengthArr[i - 1]) {
continue;
}
path.addLast(lastSmallLengthArr[i]);
//说明找到了解
if (value + lastSmallLengthArr[i] >= min && value + lastSmallLengthArr[i] <= max) {
//保存解
result.add((LinkedList<Integer>) path.clone());
}
dfs(lastSmallLengthArr, value + lastSmallLengthArr[i], min, max, i + 1, length, path, result);
path.removeLast();
}
}
}
[/code] |
|