Last Updated on March 30, 2022 by Ria Pathak
CONCEPTS USED:
Recursion
DIFFICULTY LEVEL:
Medium
PROBLEM STATEMENT(SIMPLIFIED):
Given an array containing
Nelements and an integerK, find the number of ways to calculate the value ofKusing array elements.
See original problem statement here
NOTE:
The array contains both
(-ve)and(+ve)integers.Use only
AdditionandSubtractionto 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) = 2SOLVING APPROACH:
-
The idea is to start processing array elements from
(i=0)to(i=N-1), withKas the required value. -
Check if at any point the value of
ibecomes(>= N)and the required value ofKis not equal to0, simply return0. -
Else recursively check for the three possible cases :-
- Consider current element and add it to
K(Addition Operation) - Consider current element and subtract it from
K(Subtaction Operation) - Don’t consider the current element.
- At any point if the value of
Kbecomes0, return 1.
- Consider current element and add it to
-
Finally return the total
countof 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;
/* Return total count of three cases
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;
/* Return total count of three cases
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;
/* Return total count of three cases
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.