Cod sursa(job #2915682)

Utilizator alin.gabrielAlin Gabriel Arhip alin.gabriel Data 24 iulie 2022 05:18:17
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

ofstream fout("loto.out");

vector<int> sol, v;
long long ts = 0, s;
int n;

void print_sol() {
    for (int i = 0; i < 6 ; i++)
        fout << sol[i];
    fout.close();
    exit(0);
}

bool found_sol() {
    return ts == s && sol.size() == 6;
}

void backtrack() {
    ts -= sol[sol.size() - 1];
    sol.pop_back();
}

void btk() {
    if (found_sol())
        print_sol();

    for (int i = 0; i < n ; i++) {
        if (ts + v[i] <= s && sol.size() + 1 <= 6) {
            sol.push_back(v[i]);
            ts += v[i];
            btk();
            backtrack();
        }
    }

}

int main() {
    ifstream fin("loto.in");

    fin >> n;
    fin >> s;
    int tmp;
    for (int i = 0 ; i < n; i++) {
        fin >> tmp;
        v.push_back(tmp);
    }
    fin.close();

    btk();

    fout << -1;
    fout.close();
    return 0;
}