Count of subsets of integers from 1 to N having no adjacent elements | C ++ Code to count subsets not containing adjacent elements from 1 to N ; Function to count subsets ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countSubsets ( int N ) { if ( N <= 2 ) return N ; if ( N == 3 ) return 2 ; int DP [ N + 1 ] = { 0 } ; DP [ 0 ] = 0 , DP [ 1 ] = 1 , DP [ 2 ] = 2 , DP [ 3 ] = 2 ; for ( int i = 4 ; i <= N ; i ++ ) { DP [ i ] = DP [ i - 2 ] + DP [ i - 3 ] ; } return DP [ N ] ; } int main ( ) { int N = 20 ; cout << countSubsets ( N ) ; return 0 ; }