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
< ? php $ inf = 1000000000 ; $ ans = $ inf ; function solve ( $ i , $ par , & $ a , $ n , $ k , $ current_ans ) { global $ inf , $ ans ; if ( $ par > $ k ) return ; if ( $ par == $ k && $ i == $ n - 1 ) { $ ans = min ( $ ans , $ current_ans ) ; return ; } for ( $ j = $ i + 1 ; $ j < $ n ; $ j ++ ) solve ( $ j , $ par + 1 , $ a , $ n , $ k , $ current_ans + ( $ a [ $ j ] - $ a [ $ i + 1 ] ) * ( $ a [ $ j ] - $ a [ $ i + 1 ] ) ) ; } $ k = 2 ; $ a = array ( 1 , 5 , 8 , 10 ) ; $ n = sizeof ( $ a ) ; solve ( -1 , 0 , $ a , $ n , $ k , 0 ) ; echo $ ans . " STRNEWLINE " ; ? >