Spt function or Smallest Parts Function of a given number | C ++ implementation to find the Spt Function to given number ; variable to store spt function of a number ; Function to add value of frequency of minimum element among all representations of n ; find the value of frequency of minimum element ; calculate spt ; Recursive function to find different ways in which n can be written as a sum of at one or more positive integers ; if sum becomes n , consider this representation ; start from previous element in the representation till n ; include current element from representation ; call function again with reduced sum ; backtrack - remove current element from representation ; Function to find the spt function ; Using recurrence find different ways in which n can be written as a sum of at 1 or more positive integers ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int spt = 0 ; void printVector ( vector < int > & arr ) { int min_i = INT_MAX ; for ( int i = 0 ; i < arr . size ( ) ; i ++ ) min_i = min ( min_i , arr [ i ] ) ; int freq = count ( arr . begin ( ) , arr . end ( ) , min_i ) ; spt += freq ; } void findWays ( vector < int > & arr , int i , int n ) { if ( n == 0 ) printVector ( arr ) ; for ( int j = i ; j <= n ; j ++ ) { arr . push_back ( j ) ; findWays ( arr , j , n - j ) ; arr . pop_back ( ) ; } } void spt_function ( int n ) { vector < int > arr ; findWays ( arr , 1 , n ) ; cout << spt ; } int main ( ) { int N = 4 ; spt_function ( N ) ; return 0 ; }