Individual subsequences summing a given number in an array

Question

During my current preparation for the interview, I came across a question for which I have difficulties to get the best solution,
We are given an array A and an integer Sum , we need to find all the different subsequences of A , the sum of which is equal to Sum .
E.g. A={1,2,3,5,6} Sum=6 , then the answer should be {1,2,3}
{1,5}
{6}

Currently, I can imagine two ways to do this,

• Use Recursion (which I suppose should be the last to consider interviewing)
• Use Integer Partitioning for Sum section and check if section elements are present in A

Please read my thoughts.

Answer 1

I agree with Jason. This solution comes to mind:
(complexity O(sum*|A|) if you represent the map as an array)

• Call input set A and target sum
• Has an element map B, each element of which is x:y , where x (map key) is the sum, and y (map value) is the number of ways to get to it.
• Starting, adding 0:1 to the map - there is one way to get to 0 (obviously, without using elements)
• For each element a in, consider each element x:y in B.
  
  • If x+a > sum , do nothing.
  • If an element with the key x+a already exists in B, let's say that the element x+a:z , change it to x+a:y+z .
  • If the key element does not exist, simply add x+a:y to the set.
• Find the element with the key sum , so sum:x - x is our search value.

If B is sorted (or an array), you can simply skip the rest of the elements in B during the “do nothing” step.

Tracking:

The above just gives the score, it will change it to give the actual subsequences.

In each element of B, instead of the sum, all the original elements and elements used to obtain them are stored (so that each of the elements in B has a list of pairs).

For 0:1 there are no source elements.

For x+a:y original element is x , and the element to get it is a .

During the above process, if an element with a key already exists, enter the pair x/a in the element x+a (enqueue is an O(1) operation).

If the key element does not exist, simply create a list with one x/a pair in the x+a element.

To recover, just run with sum and recursively navigate your way back.

We have to be careful with repeating sequences (we?) And repeating sequences here.

An example is not to track it:

A = {1,2,3,5,6}
sum = 6

B = 0:1

Consider 1
Add 0+1
B = 0:1, 1:1

Consider 2
Add 0+2:1 , 1+2:1
B = 0:1, 1:1, 2:1, 3:1

Consider 3
Add 0+3:1 (already exists → add 1 to it), 1+3:1 , 2+1:1 , 3+1:1
B = 0:1, 1:1, 2:1, 3:2, 4:1, 5:1, 6:1

Consider 5
B = 0:1, 1:1, 2:1, 3:2, 4:1, 5:2, 6:2
The generated amounts are discarded = 7:1, 8:2, 9:1, 10:1, 11:1

Consider 6
B = 0:1, 1:1, 2:1, 3:2, 4:1, 5:2, 6:3
The generated amounts are discarded = 7:1, 8:1, 9:2, 10:1, 11:2, 12:2

Then from 6:3 we know that we have 3 ways to get to 6.

An example is tracking:

A = {1,2,3,5,6}
sum = 6

B = 0:{}

Consider 1
B = 0:{}, 1:{0/1}

Consider 2
B = 0:{}, 1:{0/1}, 2:{0/2}, 3:{1/2}

Consider 3
B = 0:{}, 1:{0/1}, 2:{0/2}, 3:{1/2,0/3}, 4:{1/3}, 5:{2/3}, 6:{3/3}

Consider 5
B = 0:{}, 1:{0/1}, 2:{0/2}, 3:{1/2,0/3}, 4:{1/3}, 5:{2/3,0/5}, 6:{3/3,1/5} Generated amounts discarded = 7, 8, 9, 10, 11

Consider 6
B = 0:{}, 1:{0/1}, 2:{0/2}, 3:{1/2,0/3}, 4:{1/3}, 5:{2/3,0/5}, 6:{3/3,1/5,0/6} Generated amounts discarded = 7, 8, 9, 10, 11, 12

Then, turning back from 6 : (not in {} means the actual item, in {} means the map entry)

 {6} {3}+3 {1}+2+3 {0}+1+2+3 1+2+3 Output {1,2,3} {0}+3+3 3+3 Invalid - 3 is duplicate {1}+5 {0}+1+5 1+5 Output {1,5} {0}+6 6 Output {6} 

Answer 2

This is a variant of the problem of a subset of sums. The task of a subset of sums determines whether there is a subset that sums a given value. You request all subsets that add up to the given value.

The problem of the subset of sums is complex (more precisely, it is NP-Complete ), which means that your option is also difficult (this is not NP-Complete, because it is not a solution problem, but it is NP-Hard).

The classic approach to the problem of a subset of sums is either recursion or dynamic programming. Obviously, how to change a recursive solution to a subset problem to answer your option. I suggest you also take a look at the dynamic programming solution on a subset and see if you can change it for your variant (tbc: I don't know if this is really possible). This would certainly be a very valuable training exercise, regardless of whether it is possible, as it will certainly improve your understanding of dynamic programming anyway.

It will surprise me if the expected answer to your question is nothing more than a recursive solution. It’s easy to come up with an acceptable approach to the problem. It is necessary to ask a dynamic programming solution "on the fly" a little to ask.

However, you did not pay attention to a very naive approach to this problem: generate all subsets, and for each subset check whether it is summed to a given value or not. Obviously, it is exponential, but it solves the problem.

Answer 3

I assumed that this array contains various numbers. Let us define the function f (i, s) - this means that we used some numbers in the range [1, i], and the sum of the numbers used is s.

Let all values ​​be stored in a 2-dimensional matrix, i.e. in cell (i, j) we will have a value for f (i, j). Now, if the values ​​for the cells located in the upper or lower corner of the cell (i, s) are already calculated, we can calculate the value for f (i, s), i.e. f (i, s) = f (i - 1, s); I don’t accept the indexed number), but if (s> = a [i]) f (i, s) + = f (i - 1, s - a [i]). And we can use the bottom-up approach to fill the entire matrix by setting [f (0, 0) = 1; f (0, i) = 0; 1 <= i <= s], [f (i, 0) = 1; 1 <= i <= n;]. If we calculated the whole matrix, then we will get the answer in cell f (n, S); Thus, we have a common time complexity of O (n * s) and a memory complexity of O (n * s);

We can improve the memory complexity if we notice that at each iteration we only need information from the previous row, which means that we can store a 2xS matrix, not nxS. We reduced the memory complexity to linear with respect to S. This NP problem is complete, therefore we do not have a polynomial algorithm for this, and this approach is the best thing.