text: Ways to write N as sum of two or more positive integers | Set | Function to find the number of partitions of N ; Base case ; Driver code
code: def partitions ( n ) : NEW_LINE INDENT p = [ 0 ] * ( n + 1 ) NEW_LINE p [ 0 ] = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT k = 1 NEW_LINE while ( ( k * ( 3 * k - 1 ) ) / 2 <= i ) : NEW_LINE INDENT p [ i ] += ( ( 1 if k % 2 else - 1 ) * p [ i - ( k * ( 3 * k - 1 ) ) // 2 ] ) NEW_LINE if ( k > 0 ) : NEW_LINE INDENT k *= - 1 NEW_LINE DEDENT else : NEW_LINE INDENT k = 1 - k NEW_LINE DEDENT DEDENT DEDENT return p [ n ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 20 NEW_LINE print ( partitions ( N ) ) NEW_LINE DEDENT