Check whether a subsequence exists with sum equal to k if arr [ i ] > 2 * arr [ i | C ++ implementation of above approach ; Function to check whether sum of any set of the array element is equal to k or not ; Traverse the array from end to start ; if k is greater than arr [ i ] then subtract it from k ; If there is any subsequence whose sum is equal to k ; Driver code
#include <iostream> NEW_LINE using namespace std ; bool CheckForSequence ( int arr [ ] , int n , int k ) { for ( int i = n - 1 ; i >= 0 ; i -- ) { if ( k >= arr [ i ] ) k -= arr [ i ] ; } if ( k != 0 ) return false ; else return true ; } int main ( ) { int A [ ] = { 1 , 3 , 7 , 15 , 31 } ; int n = sizeof ( A ) / sizeof ( int ) ; cout << ( CheckForSequence ( A , n , 18 ) ? " True " : " False " ) << endl ; return 0 ; }