text: Ways to write N as sum of two or more positive integers | Set | C ++ implementation of above approach ; Function to find the number of partitions of N ; Base case ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; long long partitions ( int n ) { vector < long long > p ( n + 1 , 0 ) ; p [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { int k = 1 ; while ( ( k * ( 3 * k - 1 ) ) / 2 <= i ) { p [ i ] += ( k % 2 ? 1 : -1 ) * p [ i - ( k * ( 3 * k - 1 ) ) / 2 ] ; if ( k > 0 ) k *= -1 ; else k = 1 - k ; } } return p [ n ] ; } int main ( ) { int N = 20 ; cout << partitions ( N ) ; return 0 ; }