Partición de un conjunto en subconjuntos de suma igual (LeetCode 416)

Este problema nos plantea determinar si un arreglo de números enteros puede dividirse en dos subconjuntos cuya suma sea idéntica. Matemáticamente, esto equivale a encontrar un subconjunto cuya suma sea exactamente la mitad de la suma total del arreglo.

Podemos modelar este escenario como un problema de la mochila 0-1. Si la suma total es impar, es imposible realizar la partición. Si es par, nuestro objetivo es llenar una "mochila" con una capacidad igual a sumaTotal / 2. En este caso, el valor y el peso de cada elemento son iguales a su valor numérico.

Lógica de implementación

• Estado: dp[j] representa el peso máximo que podemos alcanzar en una mochila de capacidad j.
• Transición: dp[j] = max(dp[j], dp[j - num] + num).
• Condición de éxito: Si al final dp[objetivo] == objetivo, significa que encontramos elementos que suman exactamente la mitad.

#include <vector>
#include <numeric>
#include <algorithm>

class Solution {
public:
    bool canPartition(std::vector<int>& datos) {
        int sumaAcumulada = std::accumulate(datos.begin(), datos.end(), 0);
        
        // Si la suma es impar, no se puede dividir en dos partes enteras iguales
        if (sumaAcumulada % 2 != 0) return false;
        
        int meta = sumaAcumulada / 2;
        // El problema garantiza valores máximos, dimensionamos el vector DP
        std::vector<int> dp(meta + 1, 0);
        
        for (int valor : datos) {
            // Recorremos en reversa para asegurar que cada elemento se use una sola vez (0-1 Knapsack)
            for (int j = meta; j >= valor; --j) {
                dp[j] = std::max(dp[j], dp[j - valor] + valor);
            }
        }
        
        return dp[meta] == meta;
    }
};

Minimización de la diferencia en el peso de piedras (LeetCode 1049)

En este problema, al chocar dos piedras de pesos x e y, la piedra resultante tiene un peso de |x - y|. El objetivo es minimizar el peso de la última piedra. Esto es equivalente a dividir las piedras en dos grupos cuyas sumas sean lo más cercanas posible entre sí.

Si logramos que un grupo se acerque lo máximo posible a sumaTotal / 2, la diferencia entre los dos grupos será mínima. Es, nuevamente, una aplicación de la mochila 0-1.

class Solution {
public:
    int lastStoneWeightII(std::vector<int>& piedras) {
        int total = std::accumulate(piedras.begin(), piedras.end(), 0);
        int capacidadMedia = total / 2;
        
        std::vector<int> dp(capacidadMedia + 1, 0);
        
        for (int p : piedras) {
            for (int j = capacidadMedia; j >= p; --j) {
                dp[j] = std::max(dp[j], dp[j - p] + p);
            }
        }
        
        // La diferencia mínima es la resta del grupo mayor menos el grupo menor
        // Grupo menor = dp[capacidadMedia], Grupo mayor = total - dp[capacidadMedia]
        return (total - dp[capacidadMedia]) - dp[capacidadMedia];
    }
};

Cálculo de combinaciones para una suma objetivo (LeetCode 494)

Dado un arreglo y un objetivo, debemos asignar un signo '+' o '-' a cada número para que la suma total sea igual al objetivo. Este problema puede transformarse mediante álgebra simple:

Sea P el subconjunto de números con signo positivo y N el de números con signo negativo.

1. Suma(P) - Suma(N) = objetivo
2. Suma(P) + Suma(N) = sumaTotal
   Sumando ambas ecuaciones: 2 * Suma(P) = objetivo + sumaTotal
   Por lo tanto: Suma(P) = (objetivo + sumaTotal) / 2

El problema se reduce a encontrar cuántas formas existen de sumar el valor de Suma(P) usando los elementos del arreglo.

Definición del estado DP

dp[j] indica el número de combinaciones posibles para obtener una suma j. La fórmula de transición para contar combinaciones es: dp[j] += dp[j - num].

class Solution {
public:
    int findTargetSumWays(std::vector<int>& nums, int objetivo) {
        long sumaTotal = std::accumulate(nums.begin(), nums.end(), 0L);
        
        // Casos imposibles: objetivo fuera de rango o resultado no entero
        if (std::abs(objetivo) > sumaTotal) return 0;
        if ((sumaTotal + objetivo) % 2 != 0) return 0;
        
        int targetMochila = (sumaTotal + objetivo) / 2;
        std::vector<int> dp(targetMochila + 1, 0);
        
        // Caso base: hay 1 forma de sumar 0 (no elegir ningún elemento)
        dp[0] = 1;
        
        for (int n : nums) {
            for (int j = targetMochila; j >= n; --j) {
                dp[j] += dp[j - n];
            }
        }
        
        return dp[targetMochila];
    }
};