Constraints

• 0 <= len(properties) <= 200
• Each property is a tuple (id, neighborhood, capacity)
• IDs are unique integers; duplicate capacities are allowed
• 1 <= capacity <= 1000
• 0 <= groupSize <= 20000
• The sum of capacities of properties in targetNeighborhood is at most 20000

Examples

Solution

def solution(properties, targetNeighborhood, groupSize):
    from array import array

    # Edge case: an empty selection already satisfies a non-positive target.
    if groupSize <= 0:
        return []

    # Keep only properties from the requested neighborhood.
    # Each property is a tuple: (id, neighborhood, capacity).
    # Duplicate capacities are fine; IDs are assumed unique by the constraints.
    items = []
    for pid, neighborhood, capacity in properties:
        if neighborhood == targetNeighborhood:
            items.append((pid, capacity))

    if not items:
        return []

    # Sort by ID so reconstruction naturally returns IDs in ascending order
    # and can break ties lexicographically.
    items.sort(key=lambda x: x[0])

    total_capacity = sum(capacity for _, capacity in items)
    if total_capacity < groupSize:
        return []

    max_capacity = max(capacity for _, capacity in items)

    # Exact DP only needs sums up to this limit.
    # If an optimal subset uses the minimum possible number of properties,
    # then removing any selected property must make it infeasible; otherwise
    # a smaller-cardinality solution would exist. So if T is the optimal total,
    # T - chosen_capacity < groupSize for every chosen property, which implies
    # T < groupSize + chosen_capacity <= groupSize + max_capacity.
    limit = min(total_capacity, groupSize + max_capacity - 1)

    n = len(items)
    inf = n + 1

    # suf[i][s] = minimum number of properties needed to make exact sum s
    # using only items[i:]. If impossible, it stores inf.
    suf = [None] * (n + 1)
    base = array('H', [inf]) * (limit + 1)
    base[0] = 0
    suf[n] = base

    for i in range(n - 1, -1, -1):
        _, capacity = items[i]
        next_row = suf[i + 1]
        row = array('H', next_row)  # option: skip current property
        for s in range(capacity, limit + 1):
            candidate = next_row[s - capacity] + 1
            if candidate < row[s]:
                row[s] = candidate
        suf[i] = row

    # Choose the best exact total capacity:
    # 1) minimum number of properties
    # 2) among those, minimum total capacity >= groupSize
    best_count = inf
    best_sum = None
    for s in range(groupSize, limit + 1):
        count = suf[0][s]
        if count < best_count:
            best_count = count
            best_sum = s

    if best_sum is None or best_count == inf:
        return []

    # Reconstruct the lexicographically smallest ID list for (best_count, best_sum).
    # Since items are sorted by ID, greedily taking the current item whenever it can
    # still lead to an optimal solution yields the lexicographically smallest answer.
    result = []
    remaining_sum = best_sum
    remaining_count = best_count

    for i, (pid, capacity) in enumerate(items):
        if remaining_count == 0:
            break
        if remaining_sum >= capacity and suf[i + 1][remaining_sum - capacity] + 1 == remaining_count:
            result.append(pid)
            remaining_sum -= capacity
            remaining_count -= 1

    return result

Time complexity: O(n * L), where n is the number of properties in targetNeighborhood and L = min(sumCapacity, groupSize + maxCapacity - 1). Space complexity: O(n * L).

Hints

1. This is a 0/1 knapsack or subset-sum variant: exact sums matter because two solutions with the same number of properties can overshoot by different amounts.
2. After you know the optimal count and exact total capacity, sort the matching properties by ID and reconstruct greedily to get the lexicographically smallest valid ID list.