Skip to Content
CTRL K

Two Sets II

Editorial oficial (C++) 

Explicación

Descartemos primero un caso simple. ¿Cuándo no se puede construir una solución válida?

Como los dos conjuntos tienen que tener la misma suma, es evidente que ambos deben tener la mitad de 1,2,…,N1, 2, \ldots, N. Así, si N(N+1)2\frac{N(N+1)}{2}, o la suma de los primeros NN enteros positivos, no es par, entonces no es posible una solución. Para cada subconjunto, queremos que su suma sea la mitad de esta suma, o N(N+1)4\frac{N(N+1)}{4}

Esto, combinado con las cotas bajas de NN, apunta a una DP de mochila 0-1.

En vez de intentar armar una combinación de dos subconjuntos, intentemos armar una combinación de uno, ya que el otro conjunto tiene que tener todos los demás elementos.

Si dp[i][j]\texttt{dp}[i][j] = el número de formas de formar la suma jj con los números de 1...i1...i, entonces nuestras transiciones serán dp[i][j]=dp[i−1][j]+dp[i−1][j−i]\texttt{dp}[i][j] = \texttt{dp}[i - 1][j] + \texttt{dp}[i - 1][j - i], si no incluimos el elemento actual, o si lo incluimos.

Además, podríamos contar dos veces cada conjunto. Así, en vez de contar hasta NN, contaremos hasta N−1N - 1, asegurando que el NN-ésimo elemento siempre se coloque en el segundo conjunto.

Implementación

Complejidad temporal: O(N3)\mathcal{O}(N^3)

#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
int main() {
	int n;
	cin >> n;
 
	int sum_elem = n * (n + 1) / 2;
 
	// no se puede partir de forma pareja entre dos subconjuntos
	if (sum_elem & 1) {
		cout << 0 << endl;
		return 0;
	}
 
	// la suma de cada subconjunto tiene que ser la mitad de la suma total.
	sum_elem /= 2;
 
	// dp[i][j] = el número de formas de formar la suma j con los números de 1 a i
	vector<vector<int>> dp(n, vector<int>(sum_elem + 1));
 
	// caso base: hay una forma de formar una suma de cero con cero elementos.
	dp[0][0] = 1;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= sum_elem; j++) {
			// hay dp[i - 1][j] posibilidades si no incluimos el i-ésimo
			// elemento
			dp[i][j] += dp[i - 1][j];
 
			// suma previa al incluir el elemento actual
			int prev = j - i;
 
			if (prev >= 0) { dp[i][j] += dp[i - 1][prev]; }
 
			dp[i][j] %= MOD;
		}
	}
 
	cout << dp[n - 1][sum_elem] << '\n';
}
import java.io.*;
import java.util.*;
 
public class TwoSets {
	static final int MOD = (int)1e9 + 7;
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int N = io.nextInt();
		// La suma total de los N elementos.
		int totalSum = N * (N + 1) / 2;
 
		// Esto no se puede particionar en 2 subconjuntos iguales.
		if (totalSum % 2 != 0) {
			io.println(0);
			io.close();
			System.exit(0);
		}
		totalSum /= 2;
 
		/*
		 * DP[i][j] es el número de formas de formar la suma j con los primeros i
		 * elementos. El rango de 'idx' va de 0 a N-1 porque si se usan todos los
		 * elementos, los subconjuntos se contarían dos veces.
		 */
		int[][] dp = new int[N][totalSum + 1];
		dp[0][0] = 1;
		for (int idx = 0; idx < N; idx++) {
			for (int curSum = 0; curSum <= totalSum; curSum++) {
				/*
				 * Si el estado (curSum - elemento actual) es posible
				 * DP[curSum] += DP[elemento actual - 1][curSum - elemento
				 * actual]
				 */
				if (idx >= 1) {
					dp[idx][curSum] = dp[idx - 1][curSum];
					int prev = curSum - idx;
					if (prev >= 0) {
						dp[idx][curSum] += dp[idx - 1][prev];
						dp[idx][curSum] %= MOD;
					}
				}
			}
		}
		io.println(dp[N - 1][totalSum]);
		io.close();
	}
	// CodeSnip{Kattio}
}
import sys
 
MOD = 10**9 + 7
 
n = int(input())
 
sum_elem = n * (n + 1) // 2  # Suma de los elementos en [1, ..., n]
 
# Si la suma de los elementos es impar, no se puede partir de forma pareja.
if sum_elem % 2 == 1:
	print(0)
	sys.exit()
 
# dp[i][j] guarda el número de formas de un conjunto con suma j con nums [1, ..., i].
dp = [[0] * (sum_elem // 2 + 1) for _ in range(n)]
dp[0][0] = 1  # Siempre hay una forma de partir cero elementos en dos conjuntos.
 
for i in range(1, len(dp)):
	for j in range(len(dp[0])):
 
		# Hay que incluir lo mismo que con los primeros i - 1 elementos
		dp[i][j] += dp[i - 1][j]
 
		# Luego sumar todas las formas adicionales de formarlo con el j-ésimo elemento.
		if j - i >= 0:
			dp[i][j] += dp[i - 1][j - i]
 
		dp[i][j] %= MOD
 
print(dp[-1][sum_elem // 2])
Fundamentos