0
$\begingroup$

Let $ A $ be an array of $ n $ integer arrays with unknown lengths and $ s \in \mathbb{Z} $ a given number. I want to find the number of combinations of numbers from each array, such that their sum is $ s $. In set theory terms, if I have $ n $ tuples, $ A_1, A_2, \ldots A_n $, I want to find all $ (a_1, a_2, \ldots, a_n) \in \times_{k=1}^{n} A_k$ such that $ sum((a_1, a_2, \ldots, a_2)) = s $. I tried to do so by first finding the cartesian product of all the arrays, and then iterating every combination and checking its sum. The problem is that even if I have only $ 10 $ arrays with $ 10 $ elements each, the cartesian product's length would be $ 10000000000 $, which could even be too much for the browser (I'm writing it in the browser with JS) to handle, and I would have to do $ 10000000000 $ iterations, not including iterating every combination. Is there any known and more efficient algorithm for this problem?

$\endgroup$
9
  • $\begingroup$ Do you want to list them all, or count how many there are? Is this a practical problem, or do you want to know the theoretical worst-case running time? If it is a practical problem, can you tell us about how large $n$ is and about how large $s$ is and about how large each number is? Can you tell us about the motivation for this problem or the context where you encountered it? $\endgroup$
    – D.W.
    Oct 14, 2022 at 21:27
  • $\begingroup$ @D.W. I just want count how mamy there are. It is a practical question, $ n $ can be any number from $ 1 $ to $ 100 $, $ s $ can be any integer. $\endgroup$
    – talopl
    Oct 14, 2022 at 21:39
  • $\begingroup$ Are the numbers unique? Can the same number appear in the same array multiple times? $\endgroup$ Oct 14, 2022 at 21:51
  • $\begingroup$ @NarekBojikian It's an array, so a number can multiple times $\endgroup$
    – talopl
    Oct 14, 2022 at 22:24
  • $\begingroup$ Is there a lower and upper bound on each entry in the arrays? For example, are the numbers between -100 and 100? $\endgroup$ Oct 14, 2022 at 22:30

1 Answer 1

1
$\begingroup$

The problem is NP-hard. As @AspiringMat explains, even to determine whether there exists any solution at all is as hard as the partition problem: given an instance of two-partition with numbers $x_1,\dots,x_n$, let the $i$th array contain $0$ and $x_i$, set $s=(x_1+\dots+x_n)/2$, and test whether there exists any solution to your problem. Counting the number of solutions is at least as hard as determining whether there is any solution or not.

As a result, you can't expect any algorithm that will be efficient and work for all possible inputs. Instead, you'll need to consider standard methods for dealing with intractable problems, such as focusing on a particular subset of problem instances (e.g., specify the typical size of $n$, $s$, and the integers in the arrays), or accept an exponential-time algorithm.

You can study algorithms for the subset sum problem. Some of them can be adapted to your problem -- though they might take exponential time.

The problem statement is not clear about whether you want to count how many solutions exist, or to list them all. I am assuming above that you want to count the number of solutions. If you want to list them all, this can take exponential time in the worst case, as there can be exponentially many solutions (consider, e.g., the case where each array contains 0 and 1, and where $s \approx n/2$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.