 # Please try to solve this problem related to Recursion

Check the following solution.

Mike and Exam

1 Like

Thanks a lot can you also brief your approach please

Thanks for the help With pleasure. There are exactly three choices for each element in the array:

1. Add it to the required sum.
2. Don’t include it.
3. Subtract it from the required sum.

This means that the search space for an array of size N has 3^N possible states. The recursive function solve(n,k) starts at the top level with N items, arr[0…N-1] ,and K sum. A possible way is found at the base case when n = 0 and k = 0. When n > 0, the three possible choices for the next sum are checked: k-arr[n-1], k, and k+arr[n-1].

1 Like

Thanks a Lot :- https://mycode.prepbytes.com/problems/recursion/MIKEANDEXAM

I do not have access to this website. But, I am going to double check my solution, and let you know what could be the reason for this issue.

1 Like

Check the following test generator for the problem.

The recursive solution gave the same answer as the brute-force solution for 10,0000 randomly generated test.

Test Generator

Can you share the test case which generates wrong answer?

1 Like

Thanks a Lot for Your help . I am sharing the test case from that website.

## Input:-

10
7 15
-6 0 14 15 -1 1 9
5 13
-19 -18 -17 -4 -13
9 14
4 -17 -1 11 8 -8 -15 -20 -3
5 14
-18 4 -7 -20 15
6 12
-2 3 -20 -6 11 -11
9 15
4 0 -8 -20 -1 8 -10 -16 -3
6 10
-7 -20 13 0 -13 -8
9 10
-15 -4 -4 -16 10 3 6 -19 -17
8 14
5 2 13 -20 2 -3 4 -18
8 10
1 -1 -10 -6 -18 -1 -13 11

## Expected Output

39
2
217
3
9
225
0
244
89
89

45
2
241
3
11
225
0
244
89
107

My guess is that it’s something to do with (a) zeros and (b) repeated numbers. Neither the sample test case nor the question really help you determine what you’re supposed to do with either.

This is what I get for your first test case, where you’re expecting 39 as the solution: I corroborate codingknight’s answer:

``````Solution  1 : +-6 +0 +1 -9 +14 +15 = 15
Solution  2 : +-6 -0 +1 -9 +14 +15 = 15
Solution  3 : +-6 +1 -9 +14 +15 = 15
Solution  4 : +-6 --1 +0 -9 +14 +15 = 15
Solution  5 : +-6 --1 -0 -9 +14 +15 = 15
Solution  6 : +-6 --1 -9 +14 +15 = 15
Solution  7 : --6 +0 -1 +9 -14 +15 = 15
Solution  8 : --6 -0 -1 +9 -14 +15 = 15
Solution  9 : --6 -1 +9 -14 +15 = 15
Solution 10 : --6 +-1 +0 +9 -14 +15 = 15
Solution 11 : --6 +-1 -0 +9 -14 +15 = 15
Solution 12 : --6 +-1 +9 -14 +15 = 15
Solution 13 : +-1 +0 +1 +15 = 15
Solution 14 : +-1 -0 +1 +15 = 15
Solution 15 : +-1 +1 +15 = 15
Solution 16 : --1 +0 -1 +15 = 15
Solution 17 : --1 -0 -1 +15 = 15
Solution 18 : --1 -1 +15 = 15
Solution 19 : +0 +15 = 15
Solution 20 : -0 +15 = 15
Solution 21 : +15 = 15
Solution 22 : --6 +0 +1 +9 +14 -15 = 15
Solution 23 : --6 -0 +1 +9 +14 -15 = 15
Solution 24 : --6 +1 +9 +14 -15 = 15
Solution 25 : --6 --1 +0 +9 +14 -15 = 15
Solution 26 : --6 --1 -0 +9 +14 -15 = 15
Solution 27 : --6 --1 +9 +14 -15 = 15
Solution 28 : +-6 +-1 +0 -1 +9 +14 = 15
Solution 29 : +-6 +-1 -0 -1 +9 +14 = 15
Solution 30 : +-6 +-1 -1 +9 +14 = 15
Solution 31 : +0 +1 +14 = 15
Solution 32 : -0 +1 +14 = 15
Solution 33 : +1 +14 = 15
Solution 34 : --1 +0 +14 = 15
Solution 35 : --1 -0 +14 = 15
Solution 36 : --1 +14 = 15
Solution 37 : --6 +-1 +0 +1 +9 = 15
Solution 38 : --6 +-1 -0 +1 +9 = 15
Solution 39 : --6 +-1 +1 +9 = 15
Solution 40 : --6 --1 +0 -1 +9 = 15
Solution 41 : --6 --1 -0 -1 +9 = 15
Solution 42 : --6 --1 -1 +9 = 15
Solution 43 : --6 +0 +9 = 15
Solution 44 : --6 -0 +9 = 15
Solution 45 : --6 +9 = 15
``````

15 of these solutions do not use 0 at all, 15 use -0 and 15 use +0. So it’s not clear to me on what basis six solutions are considered not valid.

1 Like

Rude to respond to my own post, I suppose, but I’ve discovered the problem. The blogged solution contains a bug: because it returns ‘1’ the instant k==0, it sometimes terminates the search early. codingknight’s code (and my own code) doesn’t do this, so our figures are correct. The model answer is wrong.

1 Like

All the wrong answer cases share something interesting in common: the array has a pair of elements with the equal magnitude and different signs, e.g. 11 and -11. On the other hand, all the correct cases with non-zero answer share that the array does not have this property. Also, all wrong answers have larger value. The 5th test case has 11 distinct sums that add up to 12:

1
6 12
-2 3 -20 -6 11 -11

Possible sums:

-2 20 -6 -11 11
-2 -3 6 11
-2 3 11
-3 20 6 -11
3 20 -11
-2 20 -6
-2 -3 6 11
-2 3 11
-3 20 6 -11
3 20 -11
-2 20 -6 11 -11

The addition of 11 or -11 is considered by the brute-force solver a different way when it is added from a different element and its sign is affected by the arithmetic operation, i.e. +(-11) is not the same way as -(11), and +(11) is not the same way is -(-11).

2 Likes

Thanks a Lot for finding the bug .

This is realy a great obserbation thanks …  