java - 从两个数组中找到总和组合

Question

有两个整数数组，即 A = [2,9,8,13] 和 B = [5,3,1,11,4]，

我们知道数组的长度，我必须从数组 A 中选择一个整数，假设我选择 13，

现在我需要找出所有的组合(数组 A 中的 1 个整数和数组 B 中的 1 个或多个整数，例如数组 A 和数组 B 中选择的所有整数之和为 13 或 13 的倍数)

即

数组 A 中的“2”和数组 B 中的“11”使得 2+11=13

数组 A 中的“8”和数组 B 中的 ('1' & '4') 使得 8+1+4=13

数组 A 中的 '9' 和数组 B 中的 ('1' & '3') 使得 9+1+3=13

数组 A 中的 '13' 和数组 B 中的 ('1','3','4','5') 使得 13+1+3+4+5=26

注意:- 只能从数组 A 中选择 1 个整数，并且可以从数组 B 中选择 1 个或多于 1 个整数

我发现的唯一方法是在 if else 语句中写下所有组合，我绝对相信还有其他方法请帮助

Answer 1

我不知道这是否会很清楚，但这是我的解决方案:

public static void main(String[] args) {
    int[] A = new int[]{2,9,8,13};
    int[] B = new int[]{5,3,1,11,4};
    System.out.println(findMe(A, B));
}

private static List<List<Integer>> findMe(int[] A, int[] B) {

    List<List<Integer>> solutions = new ArrayList<List<Integer>>();
    Arrays.sort(A);
    if (A[A.length - 1] > 9) { //if the greatest is greater than 9
        for (int a1 : A) { //for all the values in A
            Collection<List<Integer>> solution = findMeNow(B, a1);
            solutions.addAll(solution);
        }
    }
    return solutions;
}

private static Collection<List<Integer>> findMeNow(int[] B, int a1) {
    List<List<Integer>> lists = new ArrayList<List<Integer>>(); //list of all possible combinations
    Set<List<Integer>> solutions = new HashSet<List<Integer>>(); //list of all possible combinations

    for (int b1 : B) {
        int currentSize = lists.size();
        for (int index = 0; index < currentSize; index++) {
            //for each sub list, create a copy, add the new element and add it to the mother list
            List<Integer> list = lists.get(index);
            List<Integer> copyList = new ArrayList<>(list);
            copyList.add(b1);
            lists.add(copyList); 
        }
        lists.add(new ArrayList<>(Arrays.asList(a1, b1)));

        //Then check the sum for each of the resulting lists
        for (List<Integer> list : lists) {
            int sum = 0;
            for (Integer value : list) {
                sum += value;
            }
            if (sum % 13 == 0) {
                solutions.add(list);
            }
        }
    }
    return solutions;
}

基本思想是“广度优先搜索”:您实际上是在构建一个包含数组 B 的元素的所有可能组合的树，例如:

1. 5
2. 5, 3, [5,3]
3. 5, 3, [5,3], [5,1], [3,1], [5,3,1], 1

等等

就所需的操作次数而言，最坏的情况相当于“所有可能的组合”，但平均而言会更好。

附言: 因为您随后需要所有可能的解决方案，所以这不再是广度优先搜索。