Example: Brute-Force Subset Check in C

// Brute-Force Subset Check
#include <stdio.h>
#include <stdbool.h> // For boolean type

// Function to check if arr2 is a subset of arr1 using brute-force
bool isSubsetBruteForce(int arr1[], int m, int arr2[], int n) {
    if (n > m) { // If arr2 is larger than arr1, it cannot be a subset
        return false;
    }

    // Create a boolean array to keep track of matched elements in arr1
    bool matched[m];
    for (int i = 0; i < m; i++) {
        matched[i] = false; // Initialize all elements as not matched
    }

    // Iterate through each element of arr2
    for (int i = 0; i < n; i++) {
        bool found = false;
        // Search for arr2[i] in arr1
        for (int j = 0; j < m; j++) {
            if (!matched[j] && arr1[j] == arr2[i]) {
                matched[j] = true; // Mark as matched
                found = true;
                break; // Move to the next element of arr2
            }
        }
        if (!found) {
            return false; // If an element of arr2 is not found in arr1, it's not a subset
        }
    }
    return true; // All elements of arr2 were found in arr1
}

int main() {
    // Step 1: Define test cases
    int arr1_a[] = {10, 5, 2, 23, 19};
    int m_a = sizeof(arr1_a) / sizeof(arr1_a[0]);
    int arr2_a[] = {19, 5, 2};
    int n_a = sizeof(arr2_a) / sizeof(arr2_a[0]);

    int arr1_b[] = {1, 2, 3, 4, 5, 6};
    int m_b = sizeof(arr1_b) / sizeof(arr1_b[0]);
    int arr2_b[] = {1, 2, 7};
    int n_b = sizeof(arr2_b) / sizeof(arr2_b[0]);
    
    int arr1_c[] = {1, 2, 2, 3};
    int m_c = sizeof(arr1_c) / sizeof(arr1_c[0]);
    int arr2_c[] = {1, 2, 2};
    int n_c = sizeof(arr2_c) / sizeof(arr2_c[0]);

    int arr1_d[] = {1, 2, 3};
    int m_d = sizeof(arr1_d) / sizeof(arr1_d[0]);
    int arr2_d[] = {1, 2, 2}; // arr2 has two 2s, arr1 has only one
    int n_d = sizeof(arr2_d) / sizeof(arr2_d[0]);

    // Step 2: Test the brute-force function
    printf("Test Case A: arr1={10,5,2,23,19}, arr2={19,5,2}\n");
    if (isSubsetBruteForce(arr1_a, m_a, arr2_a, n_a)) {
        printf("arr2 is a subset of arr1\n\n");
    } else {
        printf("arr2 is NOT a subset of arr1\n\n");
    }

    printf("Test Case B: arr1={1,2,3,4,5,6}, arr2={1,2,7}\n");
    if (isSubsetBruteForce(arr1_b, m_b, arr2_b, n_b)) {
        printf("arr2 is a subset of arr1\n\n");
    } else {
        printf("arr2 is NOT a subset of arr1\n\n");
    }

    printf("Test Case C (Multiset Success): arr1={1,2,2,3}, arr2={1,2,2}\n");
    if (isSubsetBruteForce(arr1_c, m_c, arr2_c, n_c)) {
        printf("arr2 is a subset of arr1\n\n");
    } else {
        printf("arr2 is NOT a subset of arr1\n\n");
    }

    printf("Test Case D (Multiset Failure): arr1={1,2,3}, arr2={1,2,2}\n");
    if (isSubsetBruteForce(arr1_d, m_d, arr2_d, n_d)) {
        printf("arr2 is a subset of arr1\n\n");
    } else {
        printf("arr2 is NOT a subset of arr1\n\n");
    }

    return 0;
}