Partition Equal Subset Sum

Empieza con el total. Si es impar, no existe una división, porque dos números enteros iguales suman un número par. De lo contrario, cada grupo debe sumar exactamente target = total / 2. Cuando encuentres valores que sumen target, los valores que no elegiste formarán por sí solos la otra mitad. Así que basta con una pregunta: ¿hay algún subconjunto que sume target?

Recorre los valores en orden y toma una decisión para cada uno: ponlo en el primer grupo o déjalo para el segundo. Una función auxiliar reach(i, remaining) responde si los valores desde el índice i en adelante pueden sumar remaining. Devuelve true cuando remaining llega a 0, false cuando se queda sin valores o baja de 0 y, en los demás casos, prueba ambas opciones para nums[i].

Cada subconjunto corresponde a un camino de decisiones, así que la búsqueda no puede pasar por alto ninguna división y la respuesta es correcta. Es lenta porque hay 2^n caminos, y una entrada sin división obliga a probar casi todos. Toma 199 copias de 100 y un 98: el total es 19998, nunca se alcanza el objetivo 9999 y la búsqueda prueba todas las formas de elegir como máximo 99 de los cientos, alrededor de 4 × 10^59 caminos. Incluso 40 valores dan 2^40, alrededor de 10^12 caminos.

La recursión plantea la misma pregunta una y otra vez. reach(i, remaining) depende únicamente de dos números: i, de 0 a n, y remaining, de 0 a target. Eso da como máximo (n+1) × (target+1) preguntas distintas, aproximadamente 201 × 10001 ≈ 2 × 10^6 en los límites, una cantidad lo bastante pequeña como para responderlas todas una vez.

Construye las respuestas hacia adelante en una tabla. can[i][s] indica si algunos de los primeros i valores suman s. Sin valores, solo es posible obtener la suma 0, así que la fila 0 es falsa excepto can[0][0]. El valor num = nums[i-1] ofrece dos maneras de alcanzar s: dejar fuera num, de modo que los valores anteriores ya sumen s, o incluirlo, de modo que los valores anteriores sumen s-num. Esa es toda la regla: can[i][s] = can[i-1][s] or can[i-1][s-num], donde la segunda parte solo cuenta cuando s ≥ num. Cada fila solo lee la fila anterior, así que cada valor se usa como máximo una vez.

Con [6, 1, 4, 9, 2] y el objetivo 11, las sumas alcanzables crecen de {0} a {0, 6}, luego a {0, 1, 6, 7} y después a {0, 1, 4, 5, 6, 7, 10, 11}. La suma 11 aparece después del 4 (6 + 1 + 4), y las filas posteriores la conservan. La respuesta es can[n][target]. Cada celda requiere un tiempo constante, así que tanto el tiempo como la memoria son O(n × target).

Cada fila de la tabla solo lee la fila anterior, así que basta con una fila si la actualizas en el mismo sitio: reach[s] indica si algunos de los valores vistos hasta ahora suman s. El peligro está en el orden de las actualizaciones. Si recorres s en orden ascendente, es posible que reach[s-num] ya se haya activado con el mismo num. Con [3, 9] y un objetivo de 6, el 3 marca reach[3] y luego lo lee para marcar reach[6], como si tuvieras dos 3, y respondes que es verdadero para una división que no existe.

Recorre s en orden descendente, desde target hasta num. Entonces s-num es un índice menor que este valor aún no ha tocado, así que reach[s-num] todavía contiene la respuesta de antes de que llegara num. Eso es exactamente can[i-1][s-num] de la tabla, y la única fila hace el trabajo de toda la tabla.

También puedes detenerte en cuanto reach[target] se vuelva verdadero, porque los valores posteriores solo añaden sumas alcanzables y nunca eliminan ninguna. En el peor de los casos, siguen siendo O(n × target) pasos, unos 2 × 10^6, y la memoria se reduce a target + 1 valores booleanos.