Constraints

• 0 <= N <= 30, where N is the number of packages
• 0 <= price <= 10^6 for each package
• 0 <= S <= 15, where S is the number of distinct required services after case-insensitive normalization
• The number of optimal combinations can be exponential in N, so reconstruction is inherently output-sensitive

Examples

Solution

def solution(packages, required):
    normalized_required = []
    seen = set()
    for name in required:
        key = str(name).lower()
        if key not in seen:
            seen.add(key)
            normalized_required.append(key)

    s = len(normalized_required)
    bit_index = {name: i for i, name in enumerate(normalized_required)}

    n = len(packages)
    masks = [0] * n
    prices = [0] * n

    for i, (services, price) in enumerate(packages):
        prices[i] = price
        mask = 0
        local_seen = set()
        for service in services:
            key = str(service).lower()
            if key in bit_index and key not in local_seen:
                mask |= 1 << bit_index[key]
                local_seen.add(key)
        masks[i] = mask

    full_mask = (1 << s) - 1
    INF = 10 ** 18
    dp = [[INF] * (1 << s) for _ in range(n + 1)]
    dp[n][0] = 0

    for i in range(n - 1, -1, -1):
        pkg_mask = masks[i]
        price = prices[i]
        next_row = dp[i + 1]
        row = dp[i]
        for rem in range(1 << s):
            best = next_row[rem]
            new_rem = rem & ~pkg_mask
            take_cost = price + next_row[new_rem]
            if take_cost < best:
                best = take_cost
            row[rem] = best

    min_cost = dp[0][full_mask]
    if min_cost >= INF:
        return (-1, [])

    combos = []
    path = []

    def dfs(i, rem):
        if i == n:
            if rem == 0:
                combos.append(path.copy())
            return

        best = dp[i][rem]

        if dp[i + 1][rem] == best:
            dfs(i + 1, rem)

        new_rem = rem & ~masks[i]
        if prices[i] + dp[i + 1][new_rem] == best:
            path.append(i)
            dfs(i + 1, new_rem)
            path.pop()

    dfs(0, full_mask)
    combos.sort()
    return (min_cost, combos)

Time complexity: O(N * 2^S + T), where T is the total size of the reconstructed optimal output. Space complexity: O(N * 2^S + T).

Hints

1. Map each distinct required service to a bit position. Then each package becomes a bitmask showing which required services it covers.
2. Use DP on (package_index, remaining_services_mask) to compute the minimum cost, then run a DFS that follows only transitions whose cost matches the DP optimum to reconstruct all optimal combos.