Count ways to place ' + ' and ' | Java program for the above approach ; Function to count number of ways ' + ' and ' - ' operators can be placed in front of array elements to make the sum of array elements equal to K ; Stores sum of the array ; Stores count of 0 s in A [ ] ; Traverse the array ; Update sum ; Update count of 0 s ; Conditions where no arrangements are possible which adds up to K ; Required sum ; Dp array ; Base cases ; Fill the dp array ; Return answer ; Driver Code ; Input ; Function call
import java . util . * ; class GFG { static int solve ( int A [ ] , int N , int K ) { int sum = 0 ; int c = 0 ; for ( int i = 0 ; i < N ; i ++ ) { sum += A [ i ] ; if ( A [ i ] == 0 ) c ++ ; } if ( ( K > sum ) || ( ( ( sum + K ) % 2 ) != 0 ) ) return 0 ; sum = ( sum + K ) / 2 ; int dp [ ] [ ] = new int [ N + 1 ] [ sum + 1 ] ; for ( int i = 0 ; i <= sum ; i ++ ) dp [ 0 ] [ i ] = 0 ; for ( int i = 0 ; i <= N ; i ++ ) dp [ i ] [ 0 ] = 1 ; for ( int i = 1 ; i <= N ; i ++ ) { for ( int j = 1 ; j <= sum ; j ++ ) { if ( ( A [ i - 1 ] <= j ) && ( A [ i - 1 ] != 0 ) ) dp [ i ] [ j ] = dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j - A [ i - 1 ] ] ; else dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; } } return dp [ N ] [ sum ] + ( int ) Math . pow ( 2 , c ) ; } public static void main ( String [ ] args ) { int A [ ] = { 1 , 1 , 2 , 3 } ; int N = A . length ; int K = 3 ; System . out . print ( solve ( A , N , K ) ) ; } }