INFOMAN брой 18

/*
 Задача 2: По равно
 Дадена е редица от краен брой цели положителни числа. Възможно е, някои от
 числата в редицата да са равни помежду си. Напишете програма, която разпре-
 деля числата на възможно най-голям брой подредици така, че броят на числата
 във всяка подредица да е един и същ и освен това, сумата от числата във всяка
 от тези подредици да е еднаква. Всяко число от първоначално дадената редица
 трябва да попадне в точно една от намерените подредици.

 Решение:
 Ще изпробваме всички възможности с помощта на бектрекинг. За всяко число K от
 N (броя на числата) до 1, за което K/N и сумата на всички числа се дели на
 него ще се опитаме да разделим входната редица на този брой подредици. Алго-
 ритъма е рекурсивен. Естествената оптимизация е сортиране на числата, като
 слагайки първо по-големите, нмаляме броя комбинации за изпробване. Параметъра
 на рекурсията е номера на елемента, чието място търсим, а при всяко добавяне
 на число, увеличаваме сумата и броя на елементите на подредицата в която го
 слагаме.
*/

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int sum, n;
int group_sum, group_n;
int groups;
int m, j;
int a[MAX];
int g[MAX][MAX];
int g_n[MAX];
int g_sum[MAX];

int cmp( void * a, void * b )
{
  return *(int*)b - *(int*)a;
}

void rec( int x )
{
  int i;

  if( x == n )
  {
    printf( "%d", groups );
    for( i = 0; i < groups; i++ )
    {
      printf( "\n%d", a[g[i][0]] );
      for( j = 1; j < group_n; j++ )
        printf( " %d", a[g[i][j]] );
    }
    exit( 0 );
  }
  for( i = 0; i < groups; i++ )
    if(( g_sum[i] + a[x] < group_sum && g_n[i] + 1 < group_n )
     ||( g_sum[i] + a[x] == group_sum && g_n[i] + 1 == group_n ))
    {
      g_sum[i] += a[x];
      g[i][g_n[i]++] = x;
      rec( x + 1 );
      g_sum[i] -= a[x];
      g_n[i]--;
    }
}

main()
{
  int i;
  int temp_sum, temp_n, ss;

  freopen( "equal.inp", "r", stdin );
  freopen( "equal.out", "w", stdout );

  scanf( "%d", &n );
  for( i = 0; i < n; i++ )
    scanf( "%d", &a[i] );

  qsort( a, n, sizeof( int ), cmp );
  for( i = 0; i < n; sum += a[i++] );
  for( groups = n; groups; groups-- )
  {
    if( n % groups || sum % groups )
      continue;
    group_n = n / groups,
    group_sum = sum / groups;
    rec( 0 );
  }
}