求和算法

要求

给定一个数组，一个目标值，算出所有和等于目标值的组合，组合中会出现重复值，且每个重复值只能在每个组合出现一次。

包含小数。

import java.util.*;
import java.util.stream.Collectors;


public class Sum {

    public static void main(String[] args) {

        Double[] nums = { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 5.5,0.1,  0.4, 0.5, 0.5,0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1,};

        List<Double> nlist = Arrays.asList(nums);
        Double target = 3.5;

        List<List<Double>> result = sum(nlist, target, null);
        for (List<Double> doubles : result) {
            System.out.println(Arrays.toString(new List[]{doubles}));
        }
    }


    public static List<List<Double>> sum(List<Double> nums, Double target, List<List<Double>> 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(Arrays.asList(nums.get(i), nums.get(j)));
                } else if ((nums.get(i) + nums.get(j)) < target) {
                    List<Double> p1 = new ArrayList<>();
                    p1.add(nums.get(i));
                    p1.add(nums.get(j));
                    List<Double> tempNums = new ArrayList<>(nums);
                    getMatch(p1, tempNums, j + 1, target, currentMatch, null,null);
                }
            }
        }
        return currentMatch;
    }


    public static void getMatch(List<Double> p1, List<Double> nums, int i, Double target, List<List<Double>> currentMatch, List<Integer> exclude,List<Integer> skips) {
        if (Objects.isNull(exclude)) exclude = new ArrayList<>();
        if (Objects.isNull(skips)) skips = new ArrayList<>();
        int len = nums.size();
        for (; i < len; i++) {
            int finalI = i;
            if (exclude.stream().anyMatch((e) -> e == finalI))continue;
            if (skips.stream().anyMatch((e) -> e == finalI)) continue;
            if ((getSum(p1) + nums.get(i)) == target) {
                p1.add(nums.get(i));
                currentMatch.add(p1);
                exclude.clear();
                skips.clear();
            } else if ((getSum(p1) + nums.get(i)) < target) {
                p1.add(nums.get(i));
                exclude.add(i);
                getMatch(p1, nums, 0, target, currentMatch, exclude,skips);
            }else if ((getSum(p1) + nums.get(i)) > target) {
                skips.add(i);
                getMatch(p1, nums, 0, target, currentMatch, exclude,skips);
            }
        }
    }


    static Double getSum(List<Double> r) {
        if (r.isEmpty()) {
            return 0.0;
        } else {
            return r.stream().mapToDouble(Double::doubleValue).sum();
        }
    }
}

大概思路是，O(n^2) 循环内先看前后两数的和是否为目标值，如果这两个数相加小于目标值，那么进入递归算出组合。

将已选出的组合数字在递归循环中排除。

可以确保值只被使用一次。

如果追加数字大于目标值，将该数下表记录，将下次递归循环重置，遇到该下标跳过。

优化空间还是有的，只不过我懒得看了。