#2959

Hard

LeetCode Problem Workspace

Number of Possible Sets of Closing Branches

Calculate all valid sets of branch closures while keeping remaining branches within maxDistance using bitmask and graph analysis.

bit manipulation graph heap priority queue enumeration shortest path

Problem Statement

A company has n branches connected by roads of various lengths, ensuring all branches are initially reachable. The company wants to close some branches while keeping any remaining branches within maxDistance of each other.

The goal is to count the number of possible sets of branches that can be closed so that the remaining active branches never exceed maxDistance between any pair. Distances are measured as the minimum travel length along the existing roads.

Examples

Example 1

Input: n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]]

Output: 5

The possible sets of closing branches are:

The set [2], after closing, active branches are [0,1] and they are reachable to each other within distance 2.
The set [0,1], after closing, the active branch is [2].
The set [1,2], after closing, the active branch is [0].
The set [0,2], after closing, the active branch is [1].
The set [0,1,2], after closing, there are no active branches. It can be proven, that there are only 5 possible sets of closing branches.

Example 2

Input: n = 3, maxDistance = 5, roads = [[0,1,20],[0,1,10],[1,2,2],[0,2,2]]

Output: 7

The possible sets of closing branches are:

The set [], after closing, active branches are [0,1,2] and they are reachable to each other within distance 4.
The set [0], after closing, active branches are [1,2] and they are reachable to each other within distance 2.
The set [1], after closing, active branches are [0,2] and they are reachable to each other within distance 2.
The set [0,1], after closing, the active branch is [2].
The set [1,2], after closing, the active branch is [0].
The set [0,2], after closing, the active branch is [1].
The set [0,1,2], after closing, there are no active branches. It can be proven, that there are only 7 possible sets of closing branches.

Example 3

Input: n = 1, maxDistance = 10, roads = []

Output: 2

The possible sets of closing branches are:

The set [], after closing, the active branch is [0].
The set [0], after closing, there are no active branches. It can be proven, that there are only 2 possible sets of closing branches.

Constraints

1 <= n <= 10
1 <= maxDistance <= 105
0 <= roads.length <= 1000
roads[i].length == 3
0 <= ui, vi <= n - 1
ui != vi
1 <= wi <= 1000
All branches are reachable from each other by traveling some roads.

Solution Approach

Enumerate all branch closure subsets

Use bit manipulation to generate every possible combination of branches to close. Each subset represents a different configuration, and the bitmask allows compact representation for efficient iteration.

Validate remaining branches using graph distances

For each closure subset, compute shortest paths between all remaining active branches using Floyd-Warshall or repeated Dijkstra. Discard subsets where any pair exceeds maxDistance.

Count valid closure sets

Increment a counter for each subset that satisfies the distance constraint. Return the final count as the number of possible sets of closing branches.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(2^n * n^3) if using Floyd-Warshall for each subset, since there are 2^n subsets and n^3 operations per distance check. Space complexity is O(n^2) to store the graph distances.

What Interviewers Usually Probe

Expect the candidate to recognize bitmask enumeration for all subsets of branches.
Look for correct use of shortest path algorithms to validate distances in remaining branches.
Check that candidate avoids redundant computations across similar subsets to optimize performance.

Common Pitfalls or Variants

Common pitfalls

Failing to handle subsets with zero active branches correctly.
Misapplying shortest path logic and missing the maxDistance constraint.
Inefficient recomputation of distances for each subset without caching or memoization.

Follow-up variants

Limit closure to at most k branches and count valid sets.
Change maxDistance dynamically based on branch weights or priority.
Add weighted penalties for closing certain branches and count only optimal sets.

FAQ

What is the main pattern used in Number of Possible Sets of Closing Branches?

The primary pattern is bit manipulation combined with graph shortest path checks to validate all subsets of closures.

Why is bitmask enumeration suitable for this problem?

Because n is small (up to 10), bitmasking allows generating all 2^n subsets efficiently, representing branch closures compactly.

Can Dijkstra be used instead of Floyd-Warshall here?

Yes, Dijkstra can be run for each active branch per subset, which may be more efficient for sparse graphs than Floyd-Warshall.

How do I handle the case when all branches are closed?

The empty set of active branches is valid and should be counted as one possible set of closures.

What are common mistakes to avoid?

Ignoring zero-branch subsets, miscalculating distances for remaining branches, and recomputing paths inefficiently are frequent pitfalls.

terminal

Solution

Solution 1: Binary Enumeration + Floyd Algorithm

We notice that $n \leq 10$, so we might as well consider using the method of binary enumeration to enumerate all subsets of departments.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class Solution:
    def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
        ans = 0
        for mask in range(1 << n):
            g = [[inf] * n for _ in range(n)]
            for u, v, w in roads:
                if mask >> u & 1 and mask >> v & 1:
                    g[u][v] = min(g[u][v], w)
                    g[v][u] = min(g[v][u], w)
            for k in range(n):
                if mask >> k & 1:
                    g[k][k] = 0
                    for i in range(n):
                        for j in range(n):
                            # g[i][j] = min(g[i][j], g[i][k] + g[k][j])
                            if g[i][k] + g[k][j] < g[i][j]:
                                g[i][j] = g[i][k] + g[k][j]
            if all(
                g[i][j] <= maxDistance
                for i in range(n)
                for j in range(n)
                if mask >> i & 1 and mask >> j & 1
            ):
                ans += 1
        return ans

Continue Practicing

#3594 minimum time to transport all individuals #3112 minimum time to visit disappearing nodes #3123 find edges in shortest paths