Check if sum can be formed by selecting an element for each index from two Arrays

Namachila October 13, 2025

0 0 8 minutes read

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(2^N)
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 2^N 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 i^th index and j representing the total sum till i^th 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;
}

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)

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.

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.

Output

Yes
No
Yes

Time Complexity: O(N*M)
Auxiliary Space: O(N*M)

Related Articles:

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 zambiatek!