Clustering / Partitioning an array such that sum of square differences is minimum | C ++ program to find minimum cost k partitions of array . ; 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
#include <iostream> NEW_LINE using namespace std ; const int inf = 1000000000 ; int ans = inf ; void solve ( int i , int par , int a [ ] , int n , int k , int current_ans ) { if ( par > k ) return ; if ( par == k && i == n - 1 ) { ans = min ( ans , current_ans ) ; return ; } for ( int 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 ] ) ) ; } int main ( ) { int k = 2 ; int a [ ] = { 1 , 5 , 8 , 10 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; solve ( -1 , 0 , a , n , k , 0 ) ; cout << ans << endl ; return 0 ; }