从n个集合求数x等于1个数之和

Question

我有以下问题：

我对整数集合(2

我有个数字x。

我想知道是否有一个和(可以是多个)，其中每个集合都需要精确地贡献一个数字，等于x。

示例1:

集合1：{1，2，3，5，7，8}

集合2：{2，4，4，5，6，8，9，11 23}

x: 9

在这个例子中，可能的和是5+4，另一种可能是1+8。

Example2:

收藏1：{1，1，5，7，8，9}

收藏2：{2，4，5，6，8，9}

x: 8

在本例中，不存在可能的和。数字8在两个集合中都有，但是由于所有集合都需要在求和中贡献，所以这并不重要。

我不想强加于人，所以我想递归可以让这个过程更快一些，但是我不知道从哪里开始。我正在寻找某种思路，尽管伪代码或工作代码(java)会很感激:)

Answer 1

尝尝这个。

static boolean existSum(List<Collection<Integer>> collections, int x) {
    int size = collections.size();
    return new Object() {
        boolean find(int index, int sum) {
            if (index >= size)
                return sum == x;
            for (int i : collections.get(index)) {
                int newSum = sum + i;
                if (newSum > x)
                    break;
                if (find(index + 1, newSum))
                    return true;
            }
            return false;
        }
    }.find(0, 0);
}

public static void main(String[] args) throws Exception {
    System.out.println(existSum(List.of(
        List.of(1, 2, 3, 5, 7, 8),
        List.of(2, 4, 4, 5, 6, 8, 9, 11, 23)), 9));
    System.out.println(existSum(List.of(
        List.of(1, 1, 5, 7, 8, 9),
        List.of(2, 4, 5, 6, 8, 9)), 8));
}

产出：

true
false