Check if the Sum can be formed using Tabulation
- It uses a 2D DP table, dp, with dimensions (N + 1) x (tarGet + 1) to store whether a particular sum is possible.
- Base case: It initializes the DP table such that it’s possible to achieve a sum of 0 with any array (dp[i][0] = true).
- It iterates through all possible states using two nested loops:
- The outer loop iterates through i from 1 to N (size of arrays arr1 and arr2).
- The inner loop iterates through j from 1 to tarGet.
- Inside the loops, it checks if the current state is precomputed and sets dp[i][j] to true if so.
- It checks if it can add arr1[i – 1] or arr2[i – 1] to the current sum (j) and updates dp[i][j] accordingly.
- The result is stored in dp[N][tarGet].
C++
// C++ implementation of the above approach #include <iostream> #include <vector> using namespace std; // Function to Check whether // target sum possible or not bool isNewArrayPossible( int arr1[], int arr2[], int N, int tarGet) { vector<vector< bool >> dp(N + 1, vector< bool >(tarGet + 1, false )); // Base case: It is possible to achieve a sum of 0 with any array. for ( int i = 0; i <= N; i++) { dp[i][0] = true ; } for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= tarGet; j++) { // If the current state is precomputed, set dp[i][j] to true. if (dp[i - 1][j]) { dp[i][j] = true ; } // Check if we can add arr1[i - 1] to the current sum. if (j >= arr1[i - 1]) { dp[i][j] = dp[i][j] || dp[i - 1][j - arr1[i - 1]]; } // Check if we can add arr2[i - 1] to the current sum. if (j >= arr2[i - 1]) { dp[i][j] = dp[i][j] || dp[i - 1][j - arr2[i - 1]]; } } } // If dp[N][tarGet] is true, it is possible to achieve the target sum. return dp[N][tarGet]; } // Driver Code int main() { // Input 1 int arr1[] = {3, 4}, arr2[] = {6, 5}; int N = sizeof (arr1) / sizeof (arr1[0]); int M = 10; // Function Call if (isNewArrayPossible(arr1, arr2, N, M)) { cout << "Yes" << endl; } else { cout << "No" << endl; } // Input 2 int arr3[] = {10, 10}, arr4[] = {100, 100}; int N1 = sizeof (arr3) / sizeof (arr3[0]); int M1 = 90; // Function call if (isNewArrayPossible(arr3, arr4, N1, M1)) { cout << "Yes" << endl; } else { cout << "No" << endl; } // 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 if (isNewArrayPossible(arr5, arr6, N2, M2)) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; } // This code is contributed by Tapesh(tapeshdua420) |
Java
public class IsNewArrayPossible { // Function to Check whether // target sum possible or not public static boolean isNewArrayPossible( int [] arr1, int [] arr2, int N, int target) { boolean [][] dp = new boolean [N + 1 ][target + 1 ]; // Base case: It is possible to achieve a sum of 0 with any array. for ( int i = 0 ; i <= N; i++) { dp[i][ 0 ] = true ; } for ( int i = 1 ; i <= N; i++) { for ( int j = 1 ; j <= target; j++) { // If the current state is precomputed, set dp[i][j] to true. if (dp[i - 1 ][j]) { dp[i][j] = true ; } // Check if we can add arr1[i - 1] to the current sum. if (j >= arr1[i - 1 ]) { dp[i][j] = dp[i][j] || dp[i - 1 ][j - arr1[i - 1 ]]; } // Check if we can add arr2[i - 1] to the current sum. if (j >= arr2[i - 1 ]) { dp[i][j] = dp[i][j] || dp[i - 1 ][j - arr2[i - 1 ]]; } } } // If dp[N][target] is true, it is possible to achieve the target sum. return dp[N][target]; } public static void main(String[] args) { // Input 1 int [] arr1 = { 3 , 4 }; int [] arr2 = { 6 , 5 }; int N = arr1.length; int M = 10 ; // Function call if (isNewArrayPossible(arr1, arr2, N, M)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } // Input 2 int [] arr3 = { 10 , 10 }; int [] arr4 = { 100 , 100 }; int N1 = arr3.length; int M1 = 90 ; // Function call if (isNewArrayPossible(arr3, arr4, N1, M1)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } // Input 3 int [] arr5 = { 1 , 5 , 3 , 2 }; int [] arr6 = { 8 , 7 , 4 , 6 }; int N2 = arr5.length; int M2 = 12 ; // Function call if (isNewArrayPossible(arr5, arr6, N2, M2)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } |
Python3
def is_new_array_possible(arr1, arr2, tar_get): N = len (arr1) dp = [[ False ] * (tar_get + 1 ) for _ in range (N + 1 )] # Base case: It is possible to achieve a sum of 0 with any array. for i in range (N + 1 ): dp[i][ 0 ] = True for i in range ( 1 , N + 1 ): for j in range ( 1 , tar_get + 1 ): # If the current state is precomputed, set dp[i][j] to True. if dp[i - 1 ][j]: dp[i][j] = True # Check if we can add arr1[i - 1] to the current sum. if j > = arr1[i - 1 ]: dp[i][j] = dp[i][j] or dp[i - 1 ][j - arr1[i - 1 ]] # Check if we can add arr2[i - 1] to the current sum. if j > = arr2[i - 1 ]: dp[i][j] = dp[i][j] or dp[i - 1 ][j - arr2[i - 1 ]] # If dp[N][tarGet] is True, it is possible to achieve the target sum. return dp[N][tar_get] # Driver Code # Input 1 arr1 = [ 3 , 4 ] arr2 = [ 6 , 5 ] M = 10 # Function Call if is_new_array_possible(arr1, arr2, M): print ( "Yes" ) else : print ( "No" ) # Input 2 arr3 = [ 10 , 10 ] arr4 = [ 100 , 100 ] M1 = 90 # Function call if is_new_array_possible(arr3, arr4, M1): print ( "Yes" ) else : print ( "No" ) # Input 3 arr5 = [ 1 , 5 , 3 , 2 ] arr6 = [ 8 , 7 , 4 , 6 ] M2 = 12 # Function call if is_new_array_possible(arr5, arr6, M2): print ( "Yes" ) else : print ( "No" ) |
C#
using System; class GFG { // Function to Check whether // target sum possible or not static bool IsNewArrayPossible( int [] arr1, int [] arr2, int N, int tarGet) { bool [,] dp = new bool [N + 1, tarGet + 1]; // Base case: It is possible to achieve a sum of 0 with any array. for ( int i = 0; i <= N; i++) { dp[i, 0] = true ; } for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= tarGet; j++) { // If the current state is precomputed, set dp[i, j] to true. if (dp[i - 1, j]) { dp[i, j] = true ; } // Check if we can add arr1[i - 1] to the current sum. if (j >= arr1[i - 1]) { dp[i, j] = dp[i, j] || dp[i - 1, j - arr1[i - 1]]; } // Check if we can add arr2[i - 1] to the current sum. if (j >= arr2[i - 1]) { dp[i, j] = dp[i, j] || dp[i - 1, j - arr2[i - 1]]; } } } // If dp[N, tarGet] is true, it is possible to achieve the target sum. return dp[N, tarGet]; } // Driver Code public static void Main() { // Input 1 int [] arr1 = { 3, 4 }, arr2 = { 6, 5 }; int N = arr1.Length; int M = 10; // Function Call if (IsNewArrayPossible(arr1, arr2, N, M)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } // Input 2 int [] arr3 = { 10, 10 }, arr4 = { 100, 100 }; int N1 = arr3.Length; int M1 = 90; // Function call if (IsNewArrayPossible(arr3, arr4, N1, M1)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } // Input 3 int [] arr5 = { 1, 5, 3, 2 }, arr6 = { 8, 7, 4, 6 }; int N2 = arr5.Length; int M2 = 12; // Function call if (IsNewArrayPossible(arr5, arr6, N2, M2)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } |
Javascript
function isNewArrayPossible(arr1, arr2, target) { const N = arr1.length; const dp = Array.from({ length: N + 1 }, () => Array(target + 1).fill( false )); // Base case: It is possible to achieve a sum of 0 with any array. for (let i = 0; i <= N; i++) { dp[i][0] = true ; } for (let i = 1; i <= N; i++) { for (let j = 1; j <= target; j++) { // If the current state is precomputed, set dp[i][j] to True. if (dp[i - 1][j]) { dp[i][j] = true ; } // Check if we can add arr1[i - 1] to the current sum. if (j >= arr1[i - 1]) { dp[i][j] = dp[i][j] || dp[i - 1][j - arr1[i - 1]]; } // Check if we can add arr2[i - 1] to the current sum. if (j >= arr2[i - 1]) { dp[i][j] = dp[i][j] || dp[i - 1][j - arr2[i - 1]]; } } } // If dp[N][target] is True, it is possible to achieve the target sum. return dp[N][target]; } // Driver Code // Input 1 const arr1 = [3, 4]; const arr2 = [6, 5]; const M = 10; // Function Call if (isNewArrayPossible(arr1, arr2, M)) { console.log( "Yes" ); } else { console.log( "No" ); } // Input 2 const arr3 = [10, 10]; const arr4 = [100, 100]; const M1 = 90; // Function call if (isNewArrayPossible(arr3, arr4, M1)) { console.log( "Yes" ); } else { console.log( "No" ); } // Input 3 const arr5 = [1, 5, 3, 2]; const arr6 = [8, 7, 4, 6]; const M2 = 12; // Function call if (isNewArrayPossible(arr5, arr6, M2)) { console.log( "Yes" ); } else { console.log( "No" ); } |
Yes No Yes
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Related Articles:
Check if sum can be formed by selecting an element for each index from two Arrays
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 - 1 int dp[101][100001]; // Recursive function to tell whether target // sum is possible or not 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 = 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 void 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 Code int 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; } |
Java
// Java code to implement the approach import 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. |
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 False def 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 1 arr1 = [ 3 , 4 , 6 , 5 ] N = len (arr1) M = 10 # Function Call isNewArrayPossible(arr1, N, M) # Input 2 arr3 = [ 10 , 10 , 100 , 100 ] N1 = len (arr3) M1 = 90 # Function call isNewArrayPossible(arr3, N1, M1) # Input 3 arr5 = [ 1 , 5 , 3 , 2 , 8 , 7 , 4 , 6 ] N2 = len (arr5) M2 = 12 # Function call isNewArrayPossible(arr5, N2, M2) |
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 - 1 let 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 not function 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 not function 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 1 let arr1 = [ 3, 4 ], arr2 = [ 6, 5 ]; let N = arr1.length; let M = 10; // Function Call isNewArrayPossible(arr1, arr2, N, M); // Input 2 let arr3 = [ 10, 10 ], arr4 = [ 100, 100 ]; let N1 = arr3.length; let M1 = 90; // Function call isNewArrayPossible(arr3, arr4, N1, M1); // Input 3 let arr5 = [ 1, 5, 3, 2 ], arr6 = [ 8, 7, 4, 6 ]; let N2 = arr5.length; let M2 = 12; // Function call isNewArrayPossible(arr5, arr6, N2, M2); // This code is contributed by poojaagarwal2. |
Yes No Yes
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Contact Us