1 files changed, 106 insertions, 0 deletions

diff --git a/šola/p2/dn/DN09a_63230317.c b/šola/p2/dn/DN09a_63230317.c
new file mode 100644
index 0000000..64c5e2b
--- /dev/null
+++ b/šola/p2/dn/DN09a_63230317.c
@@ -0,0 +1,106 @@
+#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);
+}