Count ways to place ' + ' and ' | 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 ; Input ; Function call
function solve ( A , N , K ) { let sum = 0 ; let c = 0 ; for ( let i = 0 ; i < N ; i ++ ) { sum += A [ i ] ; if ( A [ i ] == 0 ) c ++ ; } if ( K > sum || ( sum + K ) % 2 ) return 0 ; sum = ( sum + K ) / 2 ; let dp = new Array ( N + 1 ) ; for ( var i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( sum + 1 ) ; } for ( let i = 0 ; i <= sum ; i ++ ) dp [ 0 ] [ i ] = 0 ; for ( let i = 0 ; i <= N ; i ++ ) dp [ i ] [ 0 ] = 1 ; for ( let i = 1 ; i <= N ; i ++ ) { for ( let j = 1 ; j <= sum ; j ++ ) { if ( A [ i - 1 ] <= j && A [ i - 1 ] ) 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 ] + Math . pow ( 2 , c ) ; } let A = [ 1 , 1 , 2 , 3 ] ; let N = A . length ; let K = 3 ; document . write ( solve ( A , N , K ) ) ;