Find number x equal to sum of 1 number from n sets-CodePudding

I'm having the following problem:

I have n sorted collections of integers (2<n<10).
I have a number x.
I wanna know if there is a sum (there can be multiple), in which each set needs to contribute exactly 1 number, which is equal to x

Example 1:
Collection 1: {1, 2, 3, 5, 7, 8}
Collection 2: {2, 4, 4, 5, 6, 8, 9, 11 23}
x: 9
For this example, a possible sum is 5 4. Another possibility is 1 8.

Example2:
Collection 1: {1, 1, 5, 7, 8, 9}
Collection 2: {2, 4, 5, 6, 8, 9}
x: 8
In this example, there is no possible sum. The number 8 is in both collections but since all collections need to contribute in the summation, this doesn't matter.

I don't wanna brute force this so i'm thinking recursion could make this process a bit faster but i don't really know where to begin. I'm looking for some kind of train of thought although pseudo code or working code (java) would be appreciated :)

CodePudding user response：

Try this.

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));
}

output:

true
false