załóżmy, że masz tablicę np. {5, 0, 4, 4, 2, 8, 2, 3}
bierzesz każdy element z tablicy i liczysz sumę pozostałych:
masz 5 i {0, 4, 4, 2, 8, 2, 3}, suma = 23. 23 nie jest podzielne przez 2 czyli nie podzielisz tej tablicy na części tak że suma elementów w lewej jest równa sumie elementów z prawej. bierzesz następna liczbę z tablicy:
masz 0 i {5, 4, 4, 2, 8, 2, 3}, suma = 28. czyli musisz znaleźć taką podtablicę, że suma jej elementów = 14. jak? generujesz kolejne wariancje tablicy, najpierw 1-elementowe ({5}, {4}, {4}, ...), 2-elementowe ({5, 4}, {5, 2}, {5, 8}...), aż do (n/2)-elementowych i sprawdzasz czy suma = 14
moja implementacja w c:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define swap(x, y) do { int temp = x; x = y; y = temp; } while(0);
int perm(int *tab, int n, int k, int sum, int s) {
int i, j;
if (k == 0 && s == sum) {
return 1;
}
for (i=0; i<k; ++i) {
for (j=i; j<n; ++j) {
swap(tab[i], tab[j]);
if (perm(tab+1, n-1, k-1, sum, s+tab[i]))
return 1;
swap(tab[i], tab[j]);
}
}
return 0;
}
int check(int *tab, int n, int sum) {
int i;
int *tab2 = malloc(n*sizeof(int));
for (i=1; i<=n/2; ++i) {
memcpy(tab2, tab, n*sizeof(int));
if (perm(tab2, n, i, sum, 0)) {
memcpy(tab, tab2, n*sizeof(int));
return i; // zwraca indeks elementu dzielacego
}
}
return 0;
}
int main(void) {
//int tab[] = {5, 0, 4, 4, 2, 8, 2, 3};
int tab[] = {3, 1, 6, 8, 8};
int n = sizeof(tab)/sizeof(*tab);
int sum;
int i, j;
int q;
for (i=0; i<n; ++i) {
swap(tab[0], tab[i]);
sum = 0;
for (j=1; j<n; ++j) {
sum += tab[j];
}
if (sum % 2 == 0 && (q = check(tab+1, n-1, sum/2))) {
// lewa strona
for (j=1; j<=q; j++) {
printf("%d ", tab[j]);
}
// rownowaznik
printf ("(%d) ", tab[0]);
// prawa strona
for (j=q+1; j<n; j++) {
printf("%d ", tab[j]);
}
break;
}
swap(tab[i], tab[0]);
}
return 0;
}
EDIT: zamiast generowania wariancji można zastosować programowanie dynamiczne. patrz podobieństwo do problemu rozmieniania pieniędzy.