Larback - Retornando conhecimento

Google.

SubSet Sum Problem

Dado um conjunto de números e um valor de destino, temos de encontrar se há qualquer subconjunto cuja soma é igual ao valor de destino.

Por exemplo,se a matriz for {10, 34, 19, 27, 58, 45} e a soma alvo for 56, temos um subconjunto {10,19,27} com a soma dada. Se o valor alvo for 100, por exemplo, não teremos um subconjunto com tal valor

Uma solução simples pode ser obtida com uma busca completa. Para cada elemento do vetor devemos gerar duas chamadas recursivas, uma onde a posição atual é somada e outra onde esta posição é ignorada. Recursivamente, iremos somar todos os subconjuntos possíveis do vetor a procura do valor alvo.

#include <iostream>
using namespace std;
bool f = false;
bool sumS(int v[],int tamanho, int somaDesejada, int somaAtual = 0){
    if (somaAtual == somaDesejada) 
		return true;
		
    tamanho--;
    if (tamanho>=0){
		return sumS(v,tamanho,somaDesejada,somaAtual) || sumS(v,tamanho,somaDesejada,somaAtual+v[tamanho]); // Somei a posição atual (levo)
	} else
		return false;
}
int main() {
    int a[] = {10, 34, 19, 27, 58, 45};
    int tam = 6;
    int soma;
	cout << "Informe o valor procurado: " ;
	cin >> soma;
    if (sumS(a,tam,soma)) 
        cout << "Soma encontrada em um subvetor";
    else
        cout << "Soma NAO encontrada";
    
    return 0;
   
}
Como para cada posição do vetor temos duas chamadas, a complexidade deste algoritmo é 2^n