Check if array sum can be made K by three operations on it | C ++ Program to find if Array can have a sum of K by applying three types of possible operations on it ; Check if it is possible to achieve a sum with three operation allowed . ; If sum is negative . ; If going out of bound . ; If sum is achieved . ; If the current state is not evaluated yet . ; Replacing element with negative value of the element . ; Substracting index number from the element . ; Adding index number to the element . ; Wrapper Function ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  100 NEW_LINE int check ( int i , int sum , int n , int k , int a [ ] , int dp [ MAX ] [ MAX ] ) { if ( sum <= 0 ) return false ; if ( i >= n ) { if ( sum == k ) return true ; return false ; } if ( dp [ i ] [ sum ] != -1 ) return dp [ i ] [ sum ] ; dp [ i ] [ sum ] = check ( i + 1 , sum - 2 * a [ i ] , n , k , a , dp ) || check ( i + 1 , sum , n , k , a , dp ) ; dp [ i ] [ sum ] = check ( i + 1 , sum - ( i + 1 ) , n , k , a , dp ) || dp [ i ] [ sum ] ; dp [ i ] [ sum ] = check ( i + 1 , sum + i + 1 , n , k , a , dp ) || dp [ i ] [ sum ] ; return dp [ i ] [ sum ] ; } bool wrapper ( int n , int k , int a [ ] ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += a [ i ] ; int dp [ MAX ] [ MAX ] ; memset ( dp , -1 , sizeof ( dp ) ) ; return check ( 0 , sum , n , k , a , dp ) ; } int main ( ) { int a [ ] = { 1 , 2 , 3 , 4 } ; int n = 4 , k = 5 ; ( wrapper ( n , k , a ) ? ( cout << " Yes " ) : ( cout << " No " ) ) ; return 0 ; }