Check if it is possible to get given sum by taking one element from each row
Given a 2-D array of N rows and M columns and an integer K. The task is to find whether is it possible to take exactly one element from each row of the given array and make a total sum equal to K.
Examples:
Input: N = 2, M = 10, K = 5 arr = {{4, 0, 15, 3, 2, 20, 10, 1, 5, 4}, {4, 0, 10, 3, 2, 25, 4, 1, 5, 4}} Output: YES Explanation: Take 2 from first row and 3 from second row. 2 + 3 = 5 So, we can make 5 by taking exactly one element from each row. Input:N = 3, M = 5, K = 5 arr = {{4, 3, 4, 5, 4}, {2, 2, 3, 4, 3}, {2, 1, 3, 3, 2}} Output: NO
Approach: This problem can be solved using Dynamic Programming.
- We can make a 2-D binary array DP[][] of N rows and K columns. where DP[i][j] = 1 represents that we can make a sum equal to j by taking exactly one element from each row till i.
- So, we will iterate the array from i = [0, N], k = [0, K] and check if the current sum(k) exist or not.
- If the current sum exist then we will iterate over the column and update the array for every possible sum which is less than or equal to K.
Below is the implementation of the above approach
C++
// C++ implementation to find // whether is it possible to // make sum equal to K #include <bits/stdc++.h> using namespace std; // Function that prints whether is it // possible to make sum equal to K void PossibleSum( int n, int m, vector<vector< int > > v, int k) { int dp[n + 1][k + 1] = { 0 }; // Base case dp[0][0] = 1; for ( int i = 0; i < n; i++) { for ( int j = 0; j <= k; j++) { // Condition if we can make // sum equal to current column // by using above rows if (dp[i][j] == 1) { // Iterate through current // column and check whether // we can make sum less than // or equal to k for ( int d = 0; d < m; d++) { if ((j + v[i][d]) <= k) { dp[i + 1][j + v[i][d]] = 1; } } } } } // Printing whether is it // possible or not if (dp[n][k] == 1) cout << "YES\n" ; else cout << "NO\n" ; } // Driver Code int main() { int N = 2, M = 10, K = 5; vector<vector< int > > arr = { { 4, 0, 15, 3, 2, 20, 10, 1, 5, 4 }, { 4, 0, 10, 3, 2, 25, 4, 1, 5, 4 } }; PossibleSum(N, M, arr, K); return 0; } |
Java
// Java implementation to find // whether is it possible to // make sum equal to K import java.io.*; import java.util.*; class GFG { // Function that prints whether is it // possible to make sum equal to K static void PossibleSum( int n, int m, int [][] v, int k) { int [][] dp = new int [n + 1 ][k + 1 ]; // Base case dp[ 0 ][ 0 ] = 1 ; for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j <= k; j++) { // Condition if we can make // sum equal to current column // by using above rows if (dp[i][j] == 1 ) { // Iterate through current // column and check whether // we can make sum less than // or equal to k for ( int d = 0 ; d < m; d++) { if ((j + v[i][d]) <= k) { dp[i + 1 ][j + v[i][d]] = 1 ; } } } } } // Printing whether is it // possible or not if (dp[n][k] == 1 ) System.out.println( "YES" ); else System.out.println( "NO" ); } // Driver code public static void main(String[] args) { int N = 2 , M = 10 , K = 5 ; int [][] arr = new int [][]{ { 4 , 0 , 15 , 3 , 2 , 20 , 10 , 1 , 5 , 4 }, { 4 , 0 , 10 , 3 , 2 , 25 , 4 , 1 , 5 , 4 } }; PossibleSum(N, M, arr, K); } } // This code is contributed by coder001 |
Python3
# Python3 implementation to find # whether is it possible to # make sum equal to K # Function that prints whether is it # possible to make sum equal to K def PossibleSum(n, m, v, k): dp = [[ 0 ] * (k + 1 ) for i in range (n + 1 )] # Base case dp[ 0 ][ 0 ] = 1 for i in range (n): for j in range (k + 1 ): # Condition if we can make # sum equal to current column # by using above rows if dp[i][j] = = 1 : # Iterate through current # column and check whether # we can make sum less than # or equal to k for d in range (m): if (j + v[i][d]) < = k: dp[i + 1 ][j + v[i][d]] = 1 # Printing whether is it # possible or not if dp[n][k] = = 1 : print ( "YES" ) else : print ( "NO" ) # Driver Code N = 2 M = 10 K = 5 arr = [ [ 4 , 0 , 15 , 3 , 2 , 20 , 10 , 1 , 5 , 4 ], [ 4 , 0 , 10 , 3 , 2 , 25 , 4 , 1 , 5 , 4 ] ] PossibleSum(N, M, arr, K) # This code is contributed by divyamohan123 |
Javascript
<script> // Javascript implementation to find // whether is it possible to // make sum equal to K // Function that prints whether is it // possible to make sum equal to K function PossibleSum(n, m, v, k) { var dp = Array.from(Array(n+1), ()=>Array(k+1).fill(0)); // Base case dp[0][0] = 1; for ( var i = 0; i < n; i++) { for ( var j = 0; j <= k; j++) { // Condition if we can make // sum equal to current column // by using above rows if (dp[i][j] == 1) { // Iterate through current // column and check whether // we can make sum less than // or equal to k for ( var d = 0; d < m; d++) { if ((j + v[i][d]) <= k) { dp[i + 1][j + v[i][d]] = 1; } } } } } // Printing whether is it // possible or not if (dp[n][k] == 1) document.write( "YES" ); else document.write( "NO" ); } // Driver Code var N = 2, M = 10, K = 5; var arr = [ [ 4, 0, 15, 3, 2, 20, 10, 1, 5, 4 ], [ 4, 0, 10, 3, 2, 25, 4, 1, 5, 4 ] ]; PossibleSum(N, M, arr, K); // This code is contributed by rutvik_56. </script> |
C#
// C# implementation to find // whether is it possible to // make sum equal to K using System; class GFG{ // Function that prints whether is it // possible to make sum equal to K static void PossibleSum( int n, int m, int [,] v, int k) { int [,] dp = new int [n + 1, k + 1]; // Base case dp[0, 0] = 1; for ( int i = 0; i < n; i++) { for ( int j = 0; j <= k; j++) { // Condition if we can make // sum equal to current column // by using above rows if (dp[i, j] == 1) { // Iterate through current // column and check whether // we can make sum less than // or equal to k for ( int d = 0; d < m; d++) { if ((j + v[i, d]) <= k) { dp[i + 1, j + v[i, d]] = 1; } } } } } // Printing whether is it // possible or not if (dp[n, k] == 1) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } // Driver code public static void Main(String[] args) { int N = 2, M = 10, K = 5; int [,] arr = new int [,]{ { 4, 0, 15, 3, 2, 20, 10, 1, 5, 4 }, { 4, 0, 10, 3, 2, 25, 4, 1, 5, 4 } }; PossibleSum(N, M, arr, K); } } // This code is contributed by 29AjayKumar |
Output:
YES
Time Complexity: O(N * M * K)
Auxiliary Space: O(N*K)
Efficient Approach : using array instead of 2d matrix to optimize space complexity
In previous code we can se that dp[i][j] is dependent upon dp[i+1] or dp[i] so we can assume that dp[i] is current row and dp[i] is next row.
Implementations Steps :
- Create two vectors curr and next each of size K+1 , where K is the sum of all elements of arr.
- Initialize them with 0.
- Set the Base Case.
- Now In previous code change dp[i] to curr and change dp[i+1] to next to keep track only of the two main rows.
- After every iteration update current row to next row to iterate further.
Implementation :
C++
#include <bits/stdc++.h> using namespace std; // Function that prints whether is it // possible to make sum equal to K void PossibleSum( int n, int m, vector<vector< int > > v, int k) { // initialize 2 vectors determine two rows of DP vector< int > curr(k + 1, 0); vector< int > next(k + 1, 0); // Base case curr[0] = 1; // loop to compute all subproblems for ( int i = 0; i < n; i++) { for ( int j = 0; j <= k; j++) { // Condition if we can make // sum equal to current column // by using above rows if (curr[j] == 1) { // Iterate through current // column and check whether // we can make sum less than // or equal to k for ( int d = 0; d < m; d++) { if ((j + v[i][d]) <= k) { next[j + v[i][d]] = 1; } } } } // assiging all values of next to curr vector swap(curr, next); fill(next.begin(), next.end(), 0); } // Printing whether is it // possible or not if (curr[k] == 1) cout << "YES\n" ; else cout << "NO\n" ; } // Driver Code int main() { int N = 2, M = 10, K = 5; vector<vector< int > > arr = { { 4, 0, 15, 3, 2, 20, 10, 1, 5, 4 }, { 4, 0, 10, 3, 2, 25, 4, 1, 5, 4 } }; PossibleSum(N, M, arr, K); return 0; } |
Java
import java.util.*; public class PossibleSum { // Function that prints whether it is // possible to make sum equal to K public static void possibleSum( int n, int m, List<List<Integer> > v, int k) { // initialize 2 vectors determine two rows of DP int [] curr = new int [k + 1 ]; int [] next = new int [k + 1 ]; // Base case curr[ 0 ] = 1 ; // loop to compute all subproblems for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j <= k; j++) { // Condition if we can make // sum equal to current column // by using above rows if (curr[j] == 1 ) { // Iterate through current // column and check whether // we can make sum less than // or equal to k for ( int d = 0 ; d < m; d++) { if ((j + v.get(i).get(d)) <= k) { next[j + v.get(i).get(d)] = 1 ; } } } } // assiging all values of next to curr vector curr = Arrays.copyOf(next, k + 1 ); Arrays.fill(next, 0 ); } // Printing whether it is possible or not if (curr[k] == 1 ) System.out.println( "YES" ); else System.out.println( "NO" ); } // Driver Code public static void main(String[] args) { int N = 2 , M = 10 , K = 5 ; List<List<Integer> > arr = new ArrayList<>(); arr.add( Arrays.asList( 4 , 0 , 15 , 3 , 2 , 20 , 10 , 1 , 5 , 4 )); arr.add( Arrays.asList( 4 , 0 , 10 , 3 , 2 , 25 , 4 , 1 , 5 , 4 )); possibleSum(N, M, arr, K); } } |
Python3
from typing import List def possibleSum(n: int , m: int , v: List [ List [ int ]], k: int ) - > None : # initialize 2 vectors determine two rows of DP curr = [ 0 ] * (k + 1 ) next = [ 0 ] * (k + 1 ) # Base case curr[ 0 ] = 1 # loop to compute all subproblems for i in range (n): for j in range (k + 1 ): # Condition if we can make # sum equal to current column # by using above rows if curr[j] = = 1 : # Iterate through current # column and check whether # we can make sum less than # or equal to k for d in range (m): if j + v[i][d] < = k: next [j + v[i][d]] = 1 # assiging all values of next to curr vector curr = next .copy() next = [ 0 ] * (k + 1 ) # Printing whether it is possible or not if curr[k] = = 1 : print ( "YES" ) else : print ( "NO" ) # Driver Code if __name__ = = '__main__' : N, M, K = 2 , 10 , 5 arr = [ [ 4 , 0 , 15 , 3 , 2 , 20 , 10 , 1 , 5 , 4 ], [ 4 , 0 , 10 , 3 , 2 , 25 , 4 , 1 , 5 , 4 ] ] possibleSum(N, M, arr, K) |
C#
using System; using System.Collections.Generic; public class Program { public static void PossibleSum( int n, int m, List<List< int > > v, int k) { // initialize 2 vectors determine two rows of DP List< int > curr = new List< int >( new int [k + 1]); List< int > next = new List< int >( new int [k + 1]); // Base case curr[0] = 1; // loop to compute all subproblems for ( int i = 0; i < n; i++) { for ( int j = 0; j <= k; j++) { // Condition if we can make // sum equal to current column // by using above rows if (curr[j] == 1) { // Iterate through current // column and check whether // we can make sum less than // or equal to k for ( int d = 0; d < m; d++) { if ((j + v[i][d]) <= k) { next[j + v[i][d]] = 1; } } } } // assiging all values of next to curr vector curr = new List< int >(next); next = new List< int >( new int [k + 1]); } // Printing whether is it // possible or not if (curr[k] == 1) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } // Driver Code public static void Main() { int N = 2, M = 10, K = 5; List<List< int > > arr = new List<List< int > >{ new List< int >{ 4, 0, 15, 3, 2, 20, 10, 1, 5, 4 }, new List< int >{ 4, 0, 10, 3, 2, 25, 4, 1, 5, 4 } }; PossibleSum(N, M, arr, K); } } |
Javascript
function possibleSum(n, m, v, k) { // initialize 2 arrays determine two rows of DP let curr = Array(k + 1).fill(0); let next = Array(k + 1).fill(0); // Base case curr[0] = 1; // loop to compute all subproblems for (let i = 0; i < n; i++) { for (let j = 0; j <= k; j++) { // Condition if we can make // sum equal to current column // by using above rows if (curr[j] === 1) { // Iterate through current // column and check whether // we can make sum less than // or equal to k for (let d = 0; d < m; d++) { if (j + v[i][d] <= k) { next[j + v[i][d]] = 1; } } } } // assiging all values of next to curr array curr = [...next]; next.fill(0); } // Printing whether it is possible or not if (curr[k] === 1) { console.log( "YES" ); } else { console.log( "NO" ); } } // Driver Code const n = 2, m = 10, k = 5; const arr = [ [4, 0, 15, 3, 2, 20, 10, 1, 5, 4], [4, 0, 10, 3, 2, 25, 4, 1, 5, 4] ]; possibleSum(n, m, arr, k); |
Output
YES
Time Complexity: O(N * K)
Auxiliary Space: O(K)