Count of subsets not containing adjacent elements | C ++ implementation of the approach ; Function to return the count of possible subsets ; Total possible subsets of n sized array is ( 2 ^ n - 1 ) ; To store the required count of subsets ; Run from i 000. .0 to 111. .1 ; If current subset has consecutive elements from the array ; Driver code
#include <iostream> NEW_LINE #include <math.h> NEW_LINE using namespace std ; int cntSubsets ( int * arr , int n ) { unsigned int max = pow ( 2 , n ) ; int result = 0 ; for ( int i = 0 ; i < max ; i ++ ) { int counter = i ; if ( counter & ( counter >> 1 ) ) continue ; result ++ ; } return result ; } int main ( ) { int arr [ ] = { 3 , 5 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << cntSubsets ( arr , n ) ; return 0 ; }