//g++  7.4.0
// https://leetcode.com/discuss/interview-experience/1930164/Microsoft-or-SDE2-or-Hyderabad-or-April-2022-Reject

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> GetAllCombinations (int current_day, int repititions_left) {
    if (repititions_left == 0) return {{}};    // 1 possiblity
    if (current_day < 0) return {};           // No possibilty
    
    vector<vector<int>> result;
    vector<vector<int>> combinations_for_remaining_repitions;
    
    // take the current day
    combinations_for_remaining_repitions = GetAllCombinations (current_day-1, repititions_left-1);

    for (auto each : combinations_for_remaining_repitions) {
        each.push_back(current_day);
        result.push_back(each);
    }
    
    // don't take the current day
    combinations_for_remaining_repitions = GetAllCombinations (current_day-1, repititions_left);
    for (auto each : combinations_for_remaining_repitions) result.push_back(each);
    
    return result;
}

/*
 * availability[i] - list of days on which ith employee will be available to take the training. [0 <= availability[i][j] < D]
 *
 * total_days (D)  - total number of days in which the training can be conducted.
 *
 * repititions (R) - number of times the training will be repeated in 'total_days' duration.
 *
**/
int MaxEmployeeAttendence (vector<vector<int>>& availability, int total_days, int repititions) {
    int max_attendence = 0;
    
    vector<vector<int>> all_possible_days_for_course = GetAllCombinations (total_days-1, repititions);
    // cout << all_possible_days_for_course.size() << endl;
    
    for (vector<int> selected_days : all_possible_days_for_course) {
        unordered_set<int> selected_days_set;
        for (auto i : selected_days) selected_days_set.insert (i);
        
        int unique_employees = 0;
        for (int employee = 0; employee < availability.size(); employee ++) {
            for (int day : availability[employee]) {
                if (selected_days_set.count(day) != 0) {
                    unique_employees ++;
                    break;
                }
            }
        }

        if (max_attendence < unique_employees) max_attendence = unique_employees;
    }
    
    return max_attendence;
}

int main() {
    vector<vector<int>> availability = {
        {0, 3, 9},
        {4},
        {1, 4},
        {3, 2},
        {3, 4},
        {7}
    };
    
    cout << MaxEmployeeAttendence (availability, 10, 4) << endl;
    return 0;
}