- Arrays, Combinatorial, Dynamic Programming, Mathematical, permutation, subset

Count ways to place ‘+’ and ‘-‘ in front of array elements to obtain sum K

Count ways to place ‘+’ and ‘-‘ in front of array elements to obtain sum KGiven an array A[] consisting of N non-negative integers, and an integer K, the task is to find the number of ways ‘+’ and ‘-‘ operators can be placed in front of elements of the array A[] such that the sum of the array becomes K.Examples:Input: A[] = {1, 1, 2, 3}, N = 4, K = 1Output: 3Explanation: Three possible ways are:+ 1 + 1 + 2 – 3 = 1+ 1 – 1 – 2 + 3 = 1– 1 + 1 – 1 + 3 = 1Input: A[] = {1, 1, 1, 1, 1}, N = 5, K = 3Output: 5Approach: The problem can be solved based on the following observations:Store the sum of elements having ‘+’ in front of that element and ‘-‘ in front of that element in variables, say P1 and P2, such that the sum of the array becomes K. Store the total sum of the array A[] in a variable, say K. Therefore, following equations arises:P1 + P2 = sumP1 – P2 = K Solving the above equations obtains P1 = (sum + K) / 2.Therefore, the problem has transformed into finding the number of subsets with sum P1.If an element of A is equal to 0, both ‘+’ and ‘-‘ operators work in valid arrangements, thus, the 0s can be safely ignored and separately calculated.Hence, the problem can be solved using Dynamic Programming. Follow the steps below to solve the problem:Calculate and store the sum of elements of the array A[] and the number of 0s in A[] in variables sum and c respectively.If K is greater than sum or (sum + K) is odd, return 0.Add K to sum and divide it by 2, i.e. sum = (sum + K) / 2, which is the required sum. Find the number of subsets equal to that sum.Create a 2D dp array of dimensions N*sum. where dp[i][j] represents the number of subsets up to i-1 that have sum j.The base cases required to be considered are as follows:dp[0][i] = 0, for 0