#include <iostream>
#include <string>
using namespace std;

int numProcesses, numResources;

int maximum[10][10], allocation[10][10], need[10][10];
int available[10], finish[10], work[10];
string processNames[10];

bool is_available(int process_id) {
    for (int i = 0; i < numResources; i++) {
        if (need[process_id][i] > work[i]) {
            return false;  
        }
    }
    return true;
}

// Function to print all the safe sequences using backtracking
void safe_sequence(int count, int safeSequence[], bool marked[]) {
    if (count == numProcesses) {
        // Print the safe sequence
        for (int i = 0; i < numProcesses; i++) {
            cout << processNames[safeSequence[i]];
            if (i < numProcesses - 1)
                cout << " --> ";
        }
        cout << endl;
        return;
    }

    // Try to find a process that can be safely allocated
    for (int i = 0; i < numProcesses; i++) {
        if (!marked[i] && is_available(i)) {
            // Mark the process and add to safe sequence
            marked[i] = true;
            safeSequence[count] = i;

            int tempWork[10];
            for (int j = 0; j < numResources; j++) {
                tempWork[j] = work[j];
                work[j] += allocation[i][j];
            }

            
            safe_sequence(count + 1, safeSequence, marked);

            for (int j = 0; j < numResources; j++) {
                work[j] = tempWork[j];
            }

            marked[i] = false;
        }
    }
}

int main() {
    cout << "Enter the number of processes: ";
    cin >> numProcesses;
    cout << "Enter the number of resources: ";
    cin >> numResources;

    // Input process names
    for (int i = 0; i < numProcesses; i++) {
        cout << "Enter name for Process " << i + 1 << ": ";
        cin >> processNames[i];
    }

    // Input maximum resource matrix
    cout << "Enter the maximum resource matrix:\n";
    for (int i = 0; i < numProcesses; i++) {
        for (int j = 0; j < numResources; j++) {
            cin >> maximum[i][j];
        }
    }

    // Input allocation matrix
    cout << "Enter the allocation matrix:\n";
    for (int i = 0; i < numProcesses; i++) {
        for (int j = 0; j < numResources; j++) {
            cin >> allocation[i][j];
        }
    }

    // Input available resources
    cout << "Enter the available resources:\n";
    for (int i = 0; i < numResources; i++) {
        cin >> available[i];
    }

    // Calculate the need matrix (Need = Max - Allocated)
    for (int i = 0; i < numProcesses; i++) {
        for (int j = 0; j < numResources; j++) {
            need[i][j] = maximum[i][j] - allocation[i][j];
        }
    }

    // Initialize work array with available resources
    for (int i = 0; i < numResources; i++) {
        work[i] = available[i];
    }

    // Initialize finish array to 0 (false)
    for (int i = 0; i < numProcesses; i++) {
        finish[i] = 0;
    }

    // Array to store the safe sequence
    int safeSequence[10];
    bool marked[10] = {false}; // Array to mark the processes

    cout << "\nAll possible safe sequences are:\n";
    safe_sequence(0, safeSequence, marked);

    return 0;
}