recursividad c++ hallar todas las posibles soluciones de la suma de un vecto

[eferion]

Yo este problema lo solucionaría un poco con ayuda de contenedores, ya que una secuencia de elementos puede tener un número indeterminado de posibles soluciones, cada una de ellas con un número indeterminado de elementos (eso sí, num de elementos de la solucion <= num de elementos del vector).

La desventaja de usar, como es tu caso, un vector de bool es que el reinicio de los valores has de realizarlo con sumo cuidado si no quieres acabar mal parado.

El caso es que si cada llamada recursiva recibe un vector de elementos (la combinación que se está comprobando actualmente) es sencillo realizar todas las combinatorias.

Entonces, la función recursiva podría tener esta firma:

Código C++:

typedef std::vector<int> Items;
typedef std::vector<Items> Resultado;
 
Resultado suma( int* ptr, int totalBuscado, int contadorValoresRestantes, Items parcial);
 

Donde:

• ptr apunta al elemento actual del vector
• totalBuscado indica la suma que debemos localizar
• contadorValoresRestantes indica cuántos elementos quedan por procesar del vector
• parcial almacena la secuencia que estamos comprobando actualmente

Dado que lo que estamos pasando de forma recursiva es una combinación de elementos, parece buena idea usar una función de ayuda que sume los elementos de dicha combinación. Aunque sea una chorrada de función, mejor separar las cosas por claridad:

Código C++:

int suma(const Items& items)
{
  return std::accumulate(items.begin(),items.end(),0);
}
 

Volviendo a la función recursiva, lo que hay que hacer es probar todas las combinaciones posibles, luego cada iteración tiene que probar las combinaciones con el número actual y sin el (en el ejemplo que has puesto, los resultados válidos pueden o no incorporar el primer elemento del vector, el 8). En el caso de que añada el número a la combinación basta con actualizar parcial.

Además, sabemos que si el parcial es superior al número buscado hay que abortar esa combinación puesto que sumar más valores no va a ayudar a encontrar un resultado bueno.

Con esto la función podría quedar así:

Código C++:

Resultado suma( int* ptr, int totalBuscado, int contadorValoresRestantes, Items parcial)
{
    Resultado resultado;
 
    contadorValoresRestantes--;
    if( contadorValoresRestantes >= 0 )
    {
        // Probamos sin añadir el elemento actual
        resultado = suma((ptr+1),totalBuscado,contadorValoresRestantes,parcial);
    }
 
    // Probamos añadiendo el elemento actual
    parcial.push_back(*ptr);
    int total = suma(parcial);
    if( (total < totalBuscado) && (contadorValoresRestantes >= 0) )
    {
        Resultado resultado2 = suma(++ptr,totalBuscado,contadorValoresRestantes,parcial);
 
        // Hay que fusionar ambos resultados
        // Esta línea básicamente copia el contenido de resultado2 al final de resultado
        resultado.insert(resultado.end(),resultado2.begin(),resultado2.end());
    }
    else if( total == totalBuscado )
    {
        // Si hemos encontrado una solución, la añadimos al resultado
        resultado.push_back(parcial);
    }
 
    return resultado;
}
 

Ya está la función recursiva terminada.

Para simplificar su uso se puede hacer una función que haga las veces de entrada al algoritmo... quizás algo así:

Código C++:

Resultado suma( int* ptr, int numeroValores, int totalBuscado)
{
    return suma(ptr,totalBuscado,numeroValores-1,std::vector<int>());
}
 

Y bueno, vamos a probar el código:

Código C++:

int main()
{
  const int SIZE = 6;
  int Vector[SIZE] = {8,2,3,3,6,4}; //vector
  Resultado resultados = suma(Vector,SIZE,13);
  
  std::cout << "Resultados: " << std::endl;
  if( !resultados.empty() )
  {
    auto lambda = [&](const std::vector<int>& items)
    {
      std::string separador;
      std::for_each(items.begin(),items.end(),[&](int v){ std::cout << separador << v; separador = ","; });
      std::cout << std::endl;
    };
    
    std::for_each(resultados.begin(),resultados.end(),lambda);
  }
  else
    std::cout << "No hay resultados!!!" << std::endl;
}
 

Lo que ofrece el siguiente resultado:

Código:

Resultados:
3,6,4
3,6,4
8,2,3
8,2,3

Vaya, los resultados aparecen duplicados. ¿Es un error? En absoluto. Lo que pasa es que hay dos elementos con valor 3, lo que arroja dos resultados distintos. Si quieres eliminar esos duplicados puedes optar por soluciones un poco más sofisticadas, una posibilidad es usar el contenedor set, pero eso tendrás que investigarlo un poco antes de que te ponga una respuesta :)

Un saludo.