Spt function or Smallest Parts Function of a given number | Java implementation to find the Spt Function to given number ; Variable to store spt function of a number ; Find the value of frequency of minimum element ; 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
import java . util . * ; class GFG { static int spt = 0 ; static int count ( Vector < Integer > arr , int min_i ) { int count = 0 ; for ( int i = 0 ; i < arr . size ( ) ; i ++ ) if ( min_i == arr . get ( i ) ) count ++ ; return count ; } static void printVector ( Vector < Integer > arr ) { int min_i = Integer . MAX_VALUE ; for ( int i = 0 ; i < arr . size ( ) ; i ++ ) min_i = Math . min ( min_i , arr . elementAt ( i ) ) ; int freq = count ( arr , min_i ) ; spt += freq ; } static void findWays ( Vector < Integer > arr , int i , int n ) { if ( n == 0 ) printVector ( arr ) ; for ( int j = i ; j <= n ; j ++ ) { arr . add ( j ) ; findWays ( arr , j , n - j ) ; arr . remove ( arr . size ( ) - 1 ) ; } } static void spt_function ( int n ) { Vector < Integer > arr = new Vector < > ( ) ; findWays ( arr , 1 , n ) ; System . out . print ( spt ) ; } public static void main ( String [ ] args ) { int N = 4 ; spt_function ( N ) ; } }