给定一个数组，一个目标值，算出所有和等于目标值的组合，组合中会出现重复值，且每个重复值只能在每个组合出现一次。
包含小数。
java;gutter:true;
import java.util.*;</p>
<p>public class Match {</p>
<pre><code>public static void main(String[] args) {
Double[] nums = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 5.5, 0.5, 0.5, 0.4};
List nlist = Arrays.asList(nums);
Double target = 8.0;
List> result = sum(nlist, target, null);
for (List doubles : result) {
System.out.println(Arrays.toString(new List[]{doubles}));
}
}
public static List> sum(List nums, Double target, List> currentMatch) {
int len = nums.size();
if (Objects.isNull(currentMatch)) currentMatch = new ArrayList<>();
for (int i = 0; i < len; i++) {
if (target < nums.get(i)) continue;
for (int j = i + 1; j < nums.size(); j++) {
if (target < nums.get(j)) continue;
if (nums.get(i) + nums.get(j) == target) {
currentMatch.add(List.of(new Double[]{nums.get(i), nums.get(j)}));
} else if ((nums.get(i) + nums.get(j)) < target) {
List p1 = new ArrayList<>();
p1.add(nums.get(i));
p1.add(nums.get(j));
List tempNums = new ArrayList<>(nums);
getMatch(p1, tempNums, j + 1, target, currentMatch, null);
}
}
}
return currentMatch;
}
public static void getMatch(List p1, List nums, int i, Double target, List> currentMatch, List exclude) {
if (Objects.isNull(exclude)) exclude = new ArrayList<>();
int len = nums.size();
for (; i < len; i++) {
int finalI = i;
if (exclude.stream().anyMatch((e)-> e == finalI))continue;
if ((getSum(p1) + nums.get(i)) == target) {
p1.add(nums.get(i));
currentMatch.add(p1);
exclude.clear();
} else if ((getSum(p1) + nums.get(i)) < target) {
p1.add(nums.get(i));
exclude.add(i);
getMatch(p1, nums, i + 1, target, currentMatch, exclude);
}
}
}
static Double getSum(List r) {
if (r.isEmpty()) {
return 0.0;
} else {
return r.stream().mapToDouble(Double::doubleValue).sum();
}
}
</code></pre>
<p>}
大概思路是，O(n^2) 循环内先看前后两数的和是否为目标值，如果这两个数相加小于目标值，那么进入递归算出组合。
将已选出的组合数字在递归循环中排除。
if (exclude.stream().anyMatch((e)-> e == finalI))continue;
可以确保值只被使用一次。
优化空间还是有的，只不过我懒得看了。
Original: https://www.cnblogs.com/yangchaojie/p/16284718.html
Author: 杨超杰
Title: 求和算法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/593201/
转载文章受原作者版权保护。转载请注明原作者出处！