Clustering / Partitioning an array such that sum of square differences is minimum | Initialize answer as infinite . ; function to generate all possible answers . and compute minimum of all costs . i -- > is index of previous partition par -- > is current number of partitions a [ ] and n -- > Input array and its size current_ans -- > Cost of partitions made so far . ; If number of partitions is more than k ; If we have mad k partitions and have reached last element ; 1 ) Partition array at different points 2 ) For every point , increase count of partitions , " par " by 1. 3 ) Before recursive call , add cost of the partition to current_ans ; Driver code
inf = 1000000000 NEW_LINE ans = inf NEW_LINE def solve ( i , par , a , n , k , current_ans ) : NEW_LINE INDENT if ( par > k ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT global ans NEW_LINE if ( par == k and i == n - 1 ) : NEW_LINE INDENT ans = min ( ans , current_ans ) NEW_LINE return 0 NEW_LINE DEDENT for j in range ( i + 1 , n ) : NEW_LINE INDENT solve ( j , par + 1 , a , n , k , current_ans + ( a [ j ] - a [ i + 1 ] ) * ( a [ j ] - a [ i + 1 ] ) ) NEW_LINE DEDENT DEDENT k = 2 NEW_LINE a = [ 1 , 5 , 8 , 10 ] NEW_LINE n = len ( a ) NEW_LINE solve ( - 1 , 0 , a , n , k , 0 ) NEW_LINE print ( ans ) NEW_LINE