Given two arrays arr1[] and arr2[] of size N each. Given target sum M, Choose either a[i] or b[i] for each i where (0 ? i < N), the task is to check if it is possible to achieve the target sum print “Yes” otherwise “No“.
Examples:
Input: arr1[] = {3, 4}, arr2[] = {6, 5}, M = 10
Output: Yes
Explanation: initially sum = 0, For i = 0 choosing 6 of arr2[] in sum, sum = 6, for i = 1, choosing 4 of arr1[] in sum, sum = 10.Input: arr1[] = {10, 10}, arr2[] = {100, 100}, M = 90
Output: No
Naive Approach: The article can be solved based on the following idea:
The basic way to solve this is to generate all possible combinations by using recursive brute force and check if it is equal to target M.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve the following problem efficiently.
- dp[i][j] represents true or false value whether sum j is possible or not by using the first i elements of both arrays.
- recurrence relation : dp[i][j] = max(dp[i – 1][j + arr1[i]], dp[i – 1][j + arr2[i]])
It can be observed that there are 2 * N states but the recursive function is called 2N times. That means that some states are called repeatedly. So the idea is to store the value of states. This can be done using a recursive structure intact and just storing the value in an array or HashMap and whenever the function is called, return the value stored without computing.
Follow the steps below to solve the problem:
- Create a recursive function that takes two parameters i representing ith index and j representing the total sum till ith index.
- Call recursive function for both adding element from the first array and adding an element from the second array.
- Check the base case if the total sum j is equal to the target sum then return 1 else return 0.
- Create a 2D array of dp[101][100001] initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][j].
- If the answer for a particular state is already computed then just return dp[i][j].
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// dp table initialized with - 1int dp[101][100001];// Recursive function to tell whether target// sum is possible or notint recur(int i, int j, int tarGet, int arr1[], int arr2[], int N){ // Base case if (i == N) { // Return 1 if total sum // is equal to tarGet if (j == tarGet) return 1; else return 0; } // If current state is precomputed then // just return already computed value if (dp[i][j] != -1) return dp[i][j]; int ans = 0; // Recursive call for adding // arr1[i] in sum if (j + arr1[i] <= tarGet) ans = recur(i + 1, j + arr1[i], tarGet, arr1, arr2, N); // Recursive call for adding // arr2[i] in sum if (j + arr2[i] <= tarGet) ans = max(ans, recur(i + 1, j + arr2[i], tarGet, arr1, arr2, N)); // Save and return dp value return dp[i][j] = ans;}// Function to Check whether// target sum possible or notvoid isNewArrayPossible(int arr1[], int arr2[], int N, int tarGet){ // Filling dp table with -1 memset(dp, -1, sizeof(dp)); // If recur function returns one then // it is possible else it is not if (recur(0, 0, tarGet, arr1, arr2, N)) cout << "Yes" << endl; else cout << "No" << endl;}// Driver Codeint main(){ // Input 1 int arr1[] = { 3, 4 }, arr2[] = { 6, 5 }; int N = sizeof(arr1) / sizeof(arr1[0]); int M = 10; // Function Call isNewArrayPossible(arr1, arr2, N, M); // Input 2 int arr3[] = { 10, 10 }, arr4[] = { 100, 100 }; int N1 = sizeof(arr3) / sizeof(arr3[0]); int M1 = 90; // Function call isNewArrayPossible(arr3, arr4, N1, M1); // Input 3 int arr5[] = { 1, 5, 3, 2 }, arr6[] = { 8, 7, 4, 6 }; int N2 = sizeof(arr5) / sizeof(arr5[0]); int M2 = 12; // Function call isNewArrayPossible(arr5, arr6, N2, M2); return 0;} |
Python3
dp = [[-1 for j in range(100001)] for i in range(101)]def recur(i, j, tarGet, arr1, N): # Base case if i == N: # Return 1 if total sum is equal to tarGet if j == tarGet: return True else: return False if j > tarGet: return False if recur(i + 1, j, tarGet, arr1, N) or recur(i + 1, j + arr1[i], tarGet, arr1, N): return True else: return Falsedef isNewArrayPossible(arr1, N, tarGet): # If recur function returns one then it is possible else it is not if recur(0, 0, tarGet, arr1, N): print("Yes") else: print("No")# Input 1arr1 = [3, 4, 6, 5]N = len(arr1)M = 10# Function CallisNewArrayPossible(arr1, N, M)# Input 2arr3 = [10, 10, 100, 100]N1 = len(arr3)M1 = 90# Function callisNewArrayPossible(arr3, N1, M1)# Input 3arr5 = [1, 5, 3, 2, 8, 7, 4, 6]N2 = len(arr5)M2 = 12# Function callisNewArrayPossible(arr5, N2, M2) |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // dp table initialized with - 1 static int[][] dp = new int[101][100001]; // Recursive function to tell whether target // sum is possible or not static int recur(int i, int j, int tarGet, int[] arr1, int[] arr2, int N) { // Base case if (i == N) { // Return 1 if total sum // is equal to tarGet if (j == tarGet) return 1; else return 0; } // If current state is precomputed then // just return already computed value if (dp[i][j] != -1) return dp[i][j]; int ans = 0; // Recursive call for adding // arr1[i] in sum if (j + arr1[i] <= tarGet) ans = recur(i + 1, j + arr1[i], tarGet, arr1, arr2, N); // Recursive call for adding // arr2[i] in sum if (j + arr2[i] <= tarGet) ans = Math.max(ans, recur(i + 1, j + arr2[i], tarGet, arr1, arr2, N)); // Save and return dp value return dp[i][j] = ans; } // Function to Check whether // target sum possible or not static void isNewArrayPossible(int[] arr1, int[] arr2, int N, int tarGet) { // Filling dp table with -1 for (int i = 0; i < dp.length; i++) Arrays.fill(dp[i], -1); // If recur function returns one then // it is possible else it is not if (recur(0, 0, tarGet, arr1, arr2, N) == 1) System.out.println("Yes"); else System.out.println("No"); } public static void main(String[] args) { // Input 1 int[] arr1 = { 3, 4 }, arr2 = { 6, 5 }; int N = arr1.length; int M = 10; // Function Call isNewArrayPossible(arr1, arr2, N, M); // Input 2 int[] arr3 = { 10, 10 }, arr4 = { 100, 100 }; int N1 = arr3.length; int M1 = 90; // Function call isNewArrayPossible(arr3, arr4, N1, M1); // Input 3 int[] arr5 = { 1, 5, 3, 2 }, arr6 = { 8, 7, 4, 6 }; int N2 = arr5.length; int M2 = 12; // Function call isNewArrayPossible(arr5, arr6, N2, M2); }}// This code is contributed by lokesh. |
C#
using System;using System.Linq;public class Program{ static int[,] dp = new int[101, 100001]; // Copy code static void memset(int[,] dp, int x) { for (int i = 0; i < dp.GetLength(0); i++) { for (int j = 0; j < dp.GetLength(1); j++) dp[i, j] = -1; } } // Recursive function to tell whether target // sum is possible or not static int recur(int i, int j, int target, int[] arr1, int[] arr2, int N) { // Base case if (i == N) { // Return 1 if total sum // is equal to target if (j == target) return 1; else return 0; } // If current state is precomputed then // just return already computed value if (dp[i, j] != -1) return dp[i, j]; int ans = 0; // Recursive call for adding // arr1[i] in sum if (j + arr1[i] <= target) ans = recur(i + 1, j + arr1[i], target, arr1, arr2, N); // Recursive call for adding // arr2[i] in sum if (j + arr2[i] <= target) ans = Math.Max(ans, recur(i + 1, j + arr2[i], target, arr1, arr2, N)); // Save and return dp value return dp[i, j] = ans; } // Function to Check whether // target sum possible or not static void isNewArrayPossible(int[] arr1, int[] arr2, int N, int target) { // Filling dp table with -1 memset(dp, -1); // If recur function returns one then // it is possible else it is not if (recur(0, 0, target, arr1, arr2, N) == 1) Console.WriteLine("Yes"); else Console.WriteLine("No"); } static void Main(string[] args) { // Input 1 int[] arr1 = { 3, 4 }; int[] arr2 = { 6, 5 }; int N = arr1.Length; int M = 10; // Function Call isNewArrayPossible(arr1, arr2, N, M); // // Input 2 int[] arr3 = { 10, 10 }; int[] arr4 = { 100, 100 }; int N1 = arr3.Length; int M1 = 90; // // Function call isNewArrayPossible(arr3, arr4, N1, M1); // // Input 3 int[] arr5 = { 1, 5, 3, 2 }; int[] arr6 = { 8, 7, 4, 6 }; int N2 = arr5.Length; int M2 = 12; isNewArrayPossible(arr5, arr6, N2, M2); }} |
Javascript
// Javascriptt code to implement the approach// dp table initialized with - 1let dp = new Array(101);for(let i = 0; i < 101; i++) dp[i] = new Array(100001); function memset(dp, x){ for(let i = 0; i < dp.length; i++) { for(let j = 0; j < dp[0].length; j++) dp[i][j] = -1; }}// Recursive function to tell whether target// sum is possible or notfunction recur(i, j, tarGet, arr1, arr2, N){ // Base case if (i == N) { // Return 1 if total sum // is equal to tarGet if (j == tarGet) return 1; else return 0; } // If current state is precomputed then // just return already computed value if (dp[i][j] != -1) return dp[i][j]; let ans = 0; // Recursive call for adding // arr1[i] in sum if (j + arr1[i] <= tarGet) ans = recur(i + 1, j + arr1[i], tarGet, arr1, arr2, N); // Recursive call for adding // arr2[i] in sum if (j + arr2[i] <= tarGet) ans = Math.max(ans, recur(i + 1, j + arr2[i], tarGet, arr1, arr2, N)); // Save and return dp value return dp[i][j] = ans;}// Function to Check whether// target sum possible or notfunction isNewArrayPossible(arr1, arr2, N, tarGet){ // Filling dp table with -1 memset(dp, -1); // If recur function returns one then // it is possible else it is not if (recur(0, 0, tarGet, arr1, arr2, N)) console.log("Yes"); else console.log("No");}// Driver Code // Input 1let arr1 = [ 3, 4 ], arr2 = [ 6, 5 ];let N = arr1.length;let M = 10;// Function CallisNewArrayPossible(arr1, arr2, N, M);// Input 2let arr3 = [ 10, 10 ], arr4 = [ 100, 100 ];let N1 = arr3.length;let M1 = 90;// Function callisNewArrayPossible(arr3, arr4, N1, M1);// Input 3let arr5 = [ 1, 5, 3, 2 ], arr6 = [ 8, 7, 4, 6 ];let N2 = arr5.length;let M2 = 12;// Function callisNewArrayPossible(arr5, arr6, N2, M2);// This code is contributed by poojaagarwal2. |
Output
Yes No Yes
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Related Articles:
- Introduction to Dynamic Programming – Data Structures and Algorithm Tutorials
- Introduction to Arrays – Data Structures and Algorithm Tutorials
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
