Assignment Problem for Groups - Convert Brute Force Version to Faster Version

Question

I am writing an algorithm to assign event participants break-out rooms and prioritizing groupings of people that have not met before.

The cost matrix is 2D matrix where the number is higher if the two participants matched recently.

class Matches {
    constructor(all, group, session) {
        this.all = new Set(all);
        this.group = new Set(group);
        this.session = new Set(session);
    }
}

class User {
    constructor(id, matches) {
        this.id = id;
        this.matches = matches;
    }
}

const user00 = new User(
    0,
    new Matches([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], [4], [14])
);
const user01 = new User(1, new Matches([0], [], [13]));
const user02 = new User(2, new Matches([0, 3], [], [12]));
const user03 = new User(3, new Matches([0, 2], [], [11]));
const user04 = new User(4, new Matches([0, 5], [0], [10]));
const user05 = new User(5, new Matches([0, 4], [], [9]));
const user06 = new User(6, new Matches([0, 7], [], [8]));
const user07 = new User(7, new Matches([0, 6], [], [7]));
const user08 = new User(8, new Matches([0, 9], [], [6]));
const user09 = new User(9, new Matches([0, 8], [], [5]));
const user10 = new User(10, new Matches([0, 11], [], [4]));
const user11 = new User(11, new Matches([0, 10], [13], [3]));
const user12 = new User(12, new Matches([0, 13], [], [2]));
const user13 = new User(13, new Matches([12], [11], [1]));
const user14 = new User(14, new Matches([1], [], [0]));
const user15 = new User(14, new Matches([], [], []));

const users = [
    user00,
    user01,
    user02,
    user03,
    user04,
    user05,
    user06,
    user07,
    user08,
    user09,
    user10,
    user11,
    user12,
    user13,
    user14,
    // // user15,
];

const matchCost = 1;
const matchCostGroup = 2;
const matchCostSession = 5;

const costs = Array(users.length)
    .fill()
    .map(() => new Array(users.length).fill(0));

users.forEach((user) => {
    user.matches.all.forEach((match) => {
        if (match >= users.length) return;

        costs[user.id][match] = matchCost;
    });

    user.matches.group.forEach((match) => {
        if (match >= users.length) return;

        costs[user.id][match] += matchCostGroup;
    });

    user.matches.session.forEach((match) => {
        if (match >= users.length) return;

        costs[user.id][match] += matchCostSession;
    });
});

console.log("Costs");
console.table(costs);

const groupCost = (group) => {
    let cost = 0;
    for (let i = 0; i < group.length - 1; i++) {
        for (let j = i + 1; j < group.length; j++) {
            cost += costs[group[i]][group[j]];
        }
    }
    return cost;
};

const groupsCost = (groups) => {
    return groups.reduce((acc, group) => acc + groupCost(group), 0);
};

const assign = (numGroups, maxGroupSize) => {
    let minCost = Infinity;
    let minGroups;

    let init = Array(numGroups)
        .fill()
        .map(() => new Array(0));

    const stack = [[0, init]];

    while (stack.length > 0) {
        const [userIndex, groups] = stack.pop();

        for (let j = 0; j < groups.length; j++) {
            if (groups[j].length === maxGroupSize) {
                continue;
            }

            if (j > 0 && groups[j - 1].length === 0) {
                break;
            }

            const newGroups = [
                ...groups.slice(0, j),
                [...groups[j], userIndex],
                ...groups.slice(j + 1),
            ];

            if (userIndex === users.length - 1) {
                const thisCost = groupsCost(groups);

                if (thisCost < minCost) {
                    minCost = thisCost;
                    minGroups = newGroups;
                }
            } else {
                stack.push([userIndex + 1, newGroups]);
            }
        }
    }
    return [minCost, minGroups];
};

const numGroups = 5;
const maxGroupSize = 3;

const [minCost, minGroups] = assign(numGroups, maxGroupSize);
console.log(minCost, minGroups);

Currently, it takes up to 60 seconds to find an optimum grouping for an event of size 15. Could you please suggest the best algorithm for this problem? I am hoping to get the time down to 3-4s for an event of 100 people.

Thanks!