Dado un conjunto A de enteros y un entero s, el problema de suma exacta consiste en determinar si existe un subconjunto B ⊆ A tal que los elementos de B suman s. Necesito escribir un algoritmo polinomial no determinıstico para este problema.
Realice esto pero no se si cumpliría.
public static void main(String[] args) {
int []numeros= {1,2,3,4};
int []elegidos= new int [numeros.length];
System.out.println(buscarSubconjunto(numeros,0,numeros.length,4,elegidos));
for(int i=0;i<elegidos.length;i++)
if(elegidos[i]==1)
System.out.println(numeros[i]);
}
static boolean buscarSubconjunto(int []cifras, int j,int cantidadDeElementos,int k,int elegidos[]){
boolean temp;
if(j==cantidadDeElementos)// (* no hay más números en el conjunto *)
return false;
if (k==0)
return true;
if(cifras[j]>k)// (* el número sobre el cual se está decidiendo es mayor que el objetivo *)
return buscarSubconjunto(cifras,j+1,cantidadDeElementos,k,elegidos);
elegidos[j] =1;//(* registra que el número cifras[j] va en el subconjunto solución *)
temp = buscarSubconjunto(cifras,j+1,cantidadDeElementos,k-cifras[j],elegidos);
if (temp)
return true;
elegidos[j] = 0;// (* registra que el número cifras[j] no va en el subconjunto solución *)
return buscarSubconjunto(cifras,j+1,cantidadDeElementos,k,elegidos);
}