Итак, в основном это та же идея, что и проблема суммы подмножества, но с одним ограничением: найденное подмножество должно иметь четный размер.
Например:
numbers {4, 3, 3, 5, 1, 2, 7, 12}
find subset that sums up to 10
=> solution: {4, 3, 1, 2} (or {3, 7} but not {4, 3, 3} )
Есть ли простой способ найти такое подмножество? (Метод должен быть «эффективным», а не просто перебирать все возможные подмножества ...)
Вот мой код для поиска "нормального" подмножества:
int n = 8;
int m = 11;
boolean[][] S = new boolean[n][m];
int[] N = new int[] {4, 3, 3, 5, 1, 2, 7, 12};
S[0][0] = true;
S[0][S[0]] = true;
for(int i = 1; i < n; i++) {
for(int j = 0; j < m; j++) {
if(N[i] == j) {
S[i][j] = true;
} else if(j - N[i] >= 0) {
S[i][j] = S[i-1][j] || S[i-1][j - N[i]];
} else {
S[i][j] = S[i-1][j];
}
}
}