Question

Se citesc de la tastatură n, număr natural nenul (n≤10) şi elementele unei mulţimi A care memorează n numere întregi. Să se afişeze toate submulţimile mulţimii A={a1,a2,a3,...an} cu suma egala cu s citit

Answer 1

#include <iostream>

using namespace std;

int n, s, i, a[11];

bool sol[11];

int suma(int lvl){

   //Calculeaza suma elementelor din vector pana in prezent

   int s=0;

   for(int i=1;i<=lvl;i++){

       if(sol[i])s+=a[i];

   }

   return s;

}

void afisare(int lvl){

   //Afiseaza solutia

   int i=1;

   cout << "\n{";

   for(i=1;i<=lvl;i++){

       if(sol[i]) cout << a[i] << ", ";

   }

   cout << "\b\b}";

}

void bkt(int lvl){

   //Subprogram principal backtracking

   for(int var=0;var<=1;var++){

       sol[lvl]=var;

       int sum=suma(lvl);

       if(sum==s)afisare(lvl);

       if(lvl<=n){

           bkt(lvl+1);

       }

   }

}

int main(){

   //Citire date

   cout << "n = ", cin >> n;

   for(i=1;i<=n;i++) cin >> a[i];

   cout << "s = ", cin >> s;

   bkt(1);

}