Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Mike and Exam

Last Updated on March 30, 2022 by Ria Pathak

Recursion

Medium

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given an array containing `N` elements and an integer `K`, find the number of ways to calculate the value of `K` using array elements.

See original problem statement here

NOTE:

1. The array contains both `(-ve)` and `(+ve)` integers.

2. Use only `Addition` and `Subtraction` to accomplish the task.

#### For Example :

``````Input :

N = 4, K = 2
A = [1 3 2 6]

Output : 5

Explanation : All combinations that give 2 as output are -

1st : +(2) = 2

2nd : -(1) - (3) + (6) = 2

3rd : -(1) + (3) = 2

4th : +(1) - (2) + (3) = 2

5th : +(1) - (2) - (3) + (6) = 2``````

### SOLVING APPROACH:

1. The idea is to start processing array elements from `(i=0)` to `(i=N-1)`, with `K` as the required value.

2. Check if at any point the value of `i` becomes `(>= N)` and the required value of `K` is not equal to `0`, simply return `0`.

3. Else recursively check for the three possible cases :-

1. Consider current element and add it to `K` (`Addition Operation`)
2. Consider current element and subtract it from `K` (`Subtaction Operation`)
3. Don’t consider the current element.
4. At any point if the value of `K` becomes `0`, return 1.
4. Finally return the total `count` of the three cases.

### SOLUTIONS:

```
#include <stdio.h>

int findTotalWays(int arr[],int n,int i,int k){
/* If all elements are processed and
target is not reached, return 0 */
if(i >= n && k != 0 )
return 0;

// If target is reached, return 1
if(k == 0)
return 1;

1. Don't consider current element
2. Consider current element and subtract it from target
3. Consider current element and add it to target */
return  findTotalWays(arr,n,i+1,k)
+ findTotalWays(arr,n,i+1,k+arr[i])
+findTotalWays(arr,n,i+1,k-arr[i]);
}

int main()
{
int t;
scanf("%d",&t);
while(t--){
int n,k;
scanf("%d %d",&n,&k);
int arr[n];
int sum = 0;
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
printf("%d\n",findTotalWays(arr,n,0,k));
}
return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;

int findTotalWays(int arr[],int n,int i,int k){
/* If all elements are processed and
target is not reached, return 0 */
if(i >= n && k != 0 )
return 0;

// If target is reached, return 1
if(k == 0)
return 1;

1. Don't consider current element
2. Consider current element and subtract it from target
3. Consider current element and add it to target */
return  findTotalWays(arr,n,i+1,k)
+ findTotalWays(arr,n,i+1,k+arr[i])
+findTotalWays(arr,n,i+1,k-arr[i]);
}

int main()
{
int t;cin>>t;
while(t--){
int n,k;cin>>n>>k;
int arr[n];
int sum = 0;
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<findTotalWays(arr,n,0,k)<<"\n";
}
return 0;
}
```
```import java.util.*;
import java.io.*;

public class Main {
static int findTotalWays(int arr[],int n,int i,int k){
/* If all elements are processed and
target is not reached, return 0 */
if(i >= n && k != 0 )
return 0;

// If target is reached, return 1
if(k == 0)
return 1;

1. Don't consider current element
2. Consider current element and subtract it from target
3. Consider current element and add it to target */
return  findTotalWays(arr,n,i+1,k)
+ findTotalWays(arr,n,i+1,k+arr[i])
+findTotalWays(arr,n,i+1,k-arr[i]);
}
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t!=0){
int n = sc.nextInt();
int k = sc.nextInt();
int arr[] = new int[n];
int sum = 0;
for(int i=0;i<n;i++){
arr[i] = sc.nextInt();
}
System.out.println(findTotalWays(arr,n,0,k));
t--;
}
}
}
```
```def findTotalWays(arr, n, i, k):

if(i >= n and k != 0 ):
return 0

if( k == 0 ):
return 1

return  findTotalWays(arr,n,i+1,k) + findTotalWays(arr,n,i+1,k+arr[i])  + findTotalWays(arr,n,i+1,k-arr[i])

for _ in range(int(input())):

n, k = map(int, input().split())
arr = list(map(int, input().split()))

print(findTotalWays(arr, n, 0, k))

```

[forminator_quiz id="681"]

This article tried to discuss the concept of Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion you can check out MYCODE | Competitive Programming.