Cod sursa(job #3131857)

Utilizator bobic.teona20Bobic Teona-Christiana bobic.teona20 Data 21 mai 2023 20:10:45
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <unordered_set>
#include <vector>

using namespace std;
ifstream input("date.in");
ofstream output("date.out");
vector<int> winning_numbers;

bool backtrack(int index, int target, const vector<int>& lottery_numbers, unordered_set<int>& chosen_numbers) {
    if (target == 0 && chosen_numbers.size() == 6) {
        for (int num : chosen_numbers) {
            winning_numbers.push_back(num);
        }
        return true;
    }
    if (target < 0 || chosen_numbers.size() == 6 || index >= lottery_numbers.size()) {
        return false;
    }

    // Încercăm să includem numărul curent în combinație
    int current_num = lottery_numbers[index];
    if (chosen_numbers.find(current_num) == chosen_numbers.end()) {
        chosen_numbers.insert(current_num);
        if (backtrack(index + 1, target - current_num, lottery_numbers, chosen_numbers)) {
            return true;
        }
        chosen_numbers.erase(current_num);
    }

    // Trecem la următorul număr din listă
    return backtrack(index + 1, target, lottery_numbers, chosen_numbers);
}

void find_winning_numbers(int N, int S, const vector<int>& lottery_numbers)
{
    unordered_set<int> chosen_numbers;
    backtrack(0, S, lottery_numbers, chosen_numbers);
}

int main() {
    int N, S;
    input >> N >> S;

    vector<int> lottery_numbers(N);
    for (int i = 0; i < N; i++)
        input >> lottery_numbers[i];

    find_winning_numbers(N, S, lottery_numbers);

    if (!winning_numbers.empty())
        for (int i = 0; i < 6; i++)
            output << winning_numbers[i] << " ";
    else
        output << -1;

    return 0;
}