Check if N can be represented as sum of integers chosen from set { A , B } | CPP program to find if number N can be represented as sum of a ' s ▁ and ▁ b ' s ; Function to find if number N can be represented as sum of a ' s ▁ and ▁ b ' s ; base condition ; if x is already visited ; set x as possible ; recursive call ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; void checkIfPossibleRec ( int x , int a , int b , bool isPossible [ ] , int n ) { if ( x > n ) return ; if ( isPossible [ x ] ) return ; isPossible [ x ] = true ; checkIfPossibleRec ( x + a , a , b , isPossible , n ) ; checkIfPossibleRec ( x + b , a , b , isPossible , n ) ; } bool checkPossible ( int n , int a , int b ) { bool isPossible [ n + 1 ] = { false } ; checkIfPossibleRec ( 0 , a , b , isPossible , n ) ; return isPossible [ n ] ; } int main ( ) { int a = 3 , b = 7 , n = 8 ; if ( checkPossible ( a , b , n ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }