#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>
#define ARRSIZ 32
// komentar 2024-05-13: testi iz ucilnica2223 passajo, toda sem prepozen za oddajo
struct množica {
int n;
int arr[ARRSIZ];
};
void najdi_targete (struct množica ** shramba, int * shramba_len, int * shramba_sizeof, int n, int * t, int * stack, int globina, int target) {
if (target < 0)
return;
if (!target) {
if (*shramba_len >= *shramba_sizeof)
*shramba = realloc(*shramba, (*shramba_sizeof *= 2)*sizeof(struct množica));
memcpy((*shramba)[*shramba_len].arr, stack, sizeof(int)*globina);
(*shramba)[(*shramba_len)++].n = globina;
return;
}
for (int i = globina == 0 ? 0 : stack[globina-1]+1; i < n; i++) {
stack[globina] = i;
najdi_targete(shramba, shramba_len, shramba_sizeof, n, t, stack, globina+1, target-t[i]);
}
}
void najdi_množice (struct množica * shramba, int shramba_len, int * stack, int * t, bool * used, int n, int globina, int k) {
if (globina == k) {
for (int i = 0; i < n; i++)
if (!used[i])
return;
printf("{");
for (int i = 0; i < k; i++) {
printf("{");
int donefirst = false;
for (int j = 0; j < shramba[stack[i]].n; j++) {
printf("%s%d", donefirst ? ", " : "", t[shramba[stack[i]].arr[j]]);
donefirst = true;
}
printf("}");
if (i != k-1)
printf(", ");
}
printf("}\n");
return;
}
for (int i = globina == 0 ? 0 : stack[globina-1]+1; i < shramba_len; i++) {
bool contpls = false;
for (int j = 0; j < shramba[i].n; j++)
if (used[shramba[i].arr[j]]) {
contpls = true;
break;
}
if (contpls)
continue;
for (int j = 0; j < shramba[i].n; j++)
used[shramba[i].arr[j]] = true;
stack[globina] = i;
najdi_množice(shramba, shramba_len, stack, t, used, n, globina+1, k);
for (int j = 0; j < shramba[i].n; j++)
used[shramba[i].arr[j]] = false;
}
}
int compar (const void * a, const void * b) {
struct množica * c = ((struct množica *) a);
struct množica * d = ((struct množica *) b);
int e = INT_MAX;
int f = INT_MAX;
for (int i = 0; i < c->n; i++) {
if (c->arr[i] < e)
e = c->arr[i];
}
for (int i = 0; i < d->n; i++) {
if (d->arr[i] < f)
f = d->arr[i];
}
if (e == f)
return 0;
return e > f ? 1 : -1;
}
int main (void) {
int n, k, sum = 0;
scanf("%d %d\n", &n, &k);
int t[n];
for (int i = 0; i < n; i++) {
scanf("%d", &t[i]);
sum += t[i];
}
if (sum % k)
return 0;
int shramba_sizeof = 2;
int shramba_len = 0;
struct množica * shramba = malloc(sizeof (struct množica) * shramba_sizeof);
int stack[ARRSIZ];
najdi_targete(&shramba, &shramba_len, &shramba_sizeof, n, t, stack, 0, sum/k);
qsort(shramba, shramba_len, sizeof (struct množica), compar);
for (int i = 0; i < shramba_len; i++) {
for (int j = 0; j < shramba[i].n; j++) {
fprintf(stderr, "%d, ", t[shramba[i].arr[j]]);
}
fprintf(stderr, "\n");
}
bool used[n];
memset(used, 0, sizeof used);
najdi_množice(shramba, shramba_len, stack, t, used, n, 0, k);
}
