CONCEPTS USED:

Recursion

DIFFICULTY LEVEL:

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 go through the websites to learn programming and 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.

  5. 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;

  /* 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--;
    }
  }
}
Previous post Multiplication of Digits
Next post POWERLEX

Leave a Reply

Your email address will not be published. Required fields are marked *