search for specific value out of data set

Question

I am looking for a function or formula how to determine the data set for a specific value (sum) out of a set of data in a table. The function should be the fastest possible search to achieve the result.

Example: Search for value 41 out of the following data set

id	int
0	4
1	6
2	9
3	11
4	15

In this table, all possible combinations would be as follows

combinations with 1 field

	total (sum)
4	4
6	6
9	9
11	11
15	15

combinations with 2 fields

		total (sum)
4	6	10
4	9	13
4	11	15
4	15	19
6	9	15
6	11	17
6	15	21
9	11	20
9	15	24
11	15	26

combinations with 3 fields

			total (sum)
4	6	9	19
4	6	11	21
4	6	15	25
4	9	11	24
4	9	15	28
4	11	15	30
6	9	11	26
6	9	15	30
6	11	15	32
9	11	15	35

combinations with 4 fields

				total (sum)
4	6	9	11	30
4	6	9	15	34
4	6	11	15	36
4	9	11	15	39
6	9	11	15	41

combinations with 5 fields

					total (sum)
4	6	9	11	15	45

In this example there is one occurrence of the number 41.

Questions: what are the formulas/functions to determine

0. if the searched value (sum) appeared at all (e.g. yes or no)? (in this example yes)
1. how many times the searched value (sum) occurred? (in this example once / 1 )
2. which data sets lead to the searched value (sum) / solution? (in this example 6,9,11,15 = 41 (sum))
3. what is the fastest way to achieve the result, search through combinations or function (e.g. like sigma)?

I am unsure and curious which search algo or function would lead to the fastest result. For a binary process it might be a search function that determines the result the fastest, whereas a quantum process would determine the result in the way of patter recognition appearance.

Thank you

Answer 1

Your case 0 is known as the subset-sum problem. The others are all at least that challenging.

It's known to be NP-hard, which is to say (informally) that if there are $n$ items in your dataset, pretty much no-one expects there to be a solution that takes only $p(n)$ steps, where $p$ is any polynomial.

Wikipedia will show you several approaches to solving the problem, not with a "formula" but rather with an algorithm. The simplest one I know is recursive, and looks like this:

Given a list of numbers, $w_1, w_2, ..., w_n$ which I'll call weights, and a target, $t$, that we hope to represent as the sum of these weights, here's a procedure that consumes weights and target and produces a boolean (T/F) telling whether some subset of the weights adds up to the target, $t$.

function ss([w_1, ..., w_n], t): (list(num), num) => boolean
  if target is 0, return true // empty set has sum 0
  else if weights is empty, return false
  else if ss([w_2, ..., w_n], target) return true
  else return ss([w_2, ..., w_n), t-w1)

The explanation is this:

(i) if the target is zero, then the empty list of weights sums to the target.

(ii) If the list of weights is empty, and the target is nonzero, then there's no subset that adds up to the target.

(iii) If there's a subset of the weights that sums to the target, that subset either excludes the first element or it includes the first element.

(iv) In the first case, we can solve the problem by looking at a simpler one: solve the ss problem with a list of weights not including the first, and the original target.

(v) In the second case, we are looking for a subset of the weights that (a) includes $w_1$ and (b) sums to the target, $t$. If we took that subset and removed $w_1$, we'd have a subset that sums up to $t-w_1$. So we can check for the existence of such a subset by solving the subset-sum problem on the smaller weight-set $[w_2, \ldots, w_n]$ with the new target $t - w_1$.

A search on "subset sum problem" will yield a ton more information. Searching "quantum subset sum problem" yields several recent research papers on the topic; the one I peeked at showed how to solve the problem in exponential time, but with a smaller exponent than the solution I've written above.