LeetCode 2959 - Number of Possible Sets of Closing Branches
This problem asks us to determine the number of possible sets of branches that can be closed such that the maximum distance between any pair of remaining open branches does not exceed a given maxDistance.
Difficulty: 🔴 Hard
Topics: Bit Manipulation, Graph Theory, Heap (Priority Queue), Enumeration, Shortest Path
Solution
Problem Understanding
This problem asks us to determine the number of possible sets of branches that can be closed such that the maximum distance between any pair of remaining open branches does not exceed a given maxDistance. The input consists of n branches connected by undirected roads with given weights, where each road represents travel distance. The key aspect is that after closing any subset of branches, the remaining branches must still satisfy the maximum pairwise distance constraint.
In simpler terms, we are asked to enumerate all subsets of branches to close, including the empty set (close none) and the full set (close all), and count only those subsets where the open branches remain "well-connected" within maxDistance. If there is only one branch left or no branch left, the distance requirement is trivially satisfied.
The constraints are tight on n (maximum 10), meaning we can explore all possible subsets of branches using bitmasking (since 2^10 = 1024 subsets). The number of roads can be large, up to 1000, which affects how we compute shortest paths between branches. Since we need shortest distances between any two open branches repeatedly, we can precompute all-pairs shortest paths using Floyd-Warshall algorithm and then check each subset efficiently.
Important edge cases include when n=1 (only one branch), when roads are empty, when maxDistance is very small (no two branches can remain open), and when multiple roads exist between the same pair of branches (we must consider the shortest one).
Approaches
Brute Force
The naive approach is to generate all subsets of branches to close. For each subset, compute the shortest paths between all remaining open branches, then check whether all pairwise distances are within maxDistance. If they are, count this subset.
This is correct because it explicitly enumerates all possible closing configurations and validates the distance constraint. However, computing shortest paths for each subset is expensive. With 2^n subsets and up to n^3 for Floyd-Warshall per subset, the time complexity would be prohibitive even for n=10 if implemented naively.
Optimal Approach
The key insight is that the graph and road weights are static. Therefore, we can precompute the all-pairs shortest paths once for the original graph using Floyd-Warshall. For each subset of branches to close, we only need to check the distances in the precomputed distance matrix for the active branches. This reduces redundant computation and allows us to handle all subsets efficiently.
The approach can be summarized as:
- Precompute shortest distances between every pair of branches using Floyd-Warshall.
- Enumerate all subsets of branches to close.
- For each subset, derive the set of active branches.
- Check all pairwise distances between active branches. If all are ≤
maxDistance, include this subset in the count.
Because n ≤ 10, enumerating 2^n subsets is feasible, and checking all pairs for each subset is also feasible (O(n^2) per subset).
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n * n^3) | O(n^2) | Compute shortest paths for each subset |
| Optimal | O(n^3 + 2^n * n^2) | O(n^2) | Precompute all-pairs shortest paths and check subsets |
Algorithm Walkthrough
- Initialize an
n x ndistance matrixdistwith infinity for all pairs except diagonal elements (distance to itself is 0). - Populate the distance matrix using the given
roads. For multiple roads between the same pair, use the minimum weight. - Apply the Floyd-Warshall algorithm to compute shortest distances between all pairs of branches.
- Initialize a counter
count = 0. - Iterate through all subsets of branches to close. This can be done using bitmasking from 0 to 2^n - 1.
- For each subset, determine the set of active branches (those not included in the closing subset).
- If the active branch set has 0 or 1 branch, increment the counter directly (distance condition trivially satisfied).
- Otherwise, check all pairs of active branches using the precomputed distance matrix. If all distances are ≤
maxDistance, increment the counter. - Return the counter after all subsets have been processed.
Why it works: Precomputing the shortest paths ensures we can quickly check any subset of active branches. Enumerating all subsets guarantees that all possible closing configurations are considered. The Floyd-Warshall algorithm guarantees that distances between any two branches are minimal, so the distance check is correct for any subset.
Python Solution
from typing import List
class Solution:
def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
# Step 1: Initialize distance matrix
INF = float('inf')
dist = [[INF] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
# Step 2: Populate with given roads (minimum distance if multiple roads exist)
for u, v, w in roads:
dist[u][v] = min(dist[u][v], w)
dist[v][u] = min(dist[v][u], w)
# Step 3: Floyd-Warshall to compute all-pairs shortest paths
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
# Step 4: Enumerate all subsets of branches to close
count = 0
for mask in range(1 << n):
active = [i for i in range(n) if not (mask & (1 << i))]
valid = True
if len(active) <= 1:
count += 1
continue
for i in range(len(active)):
for j in range(i + 1, len(active)):
if dist[active[i]][active[j]] > maxDistance:
valid = False
break
if not valid:
break
if valid:
count += 1
return count
Explanation: We first build the distance matrix, accounting for multiple roads. Floyd-Warshall ensures all shortest paths are computed. Then we iterate through all 2^n subsets of branches to close and check active branches for the distance condition. Subsets with ≤1 active branch are trivially valid. The result is accumulated in count.
Go Solution
func numberOfSets(n int, maxDistance int, roads [][]int) int {
INF := 1 << 60
dist := make([][]int, n)
for i := 0; i < n; i++ {
dist[i] = make([]int, n)
for j := 0; j < n; j++ {
if i == j {
dist[i][j] = 0
} else {
dist[i][j] = INF
}
}
}
for _, road := range roads {
u, v, w := road[0], road[1], road[2]
if w < dist[u][v] {
dist[u][v] = w
dist[v][u] = w
}
}
// Floyd-Warshall
for k := 0; k < n; k++ {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if dist[i][k]+dist[k][j] < dist[i][j] {
dist[i][j] = dist[i][k] + dist[k][j]
}
}
}
}
count := 0
for mask := 0; mask < (1 << n); mask++ {
active := []int{}
for i := 0; i < n; i++ {
if mask&(1<<i) == 0 {
active = append(active, i)
}
}
valid := true
if len(active) <= 1 {
count++
continue
}
for i := 0; i < len(active); i++ {
for j := i + 1; j < len(active); j++ {
if dist[active[i]][active[j]] > maxDistance {
valid = false
break
}
}
if !valid {
break
}
}
if valid {
count++
}
}
return count
}
Explanation: The Go version mirrors the Python logic closely. We use slices for the distance matrix and active branches. The integer overflow is handled by using a large constant INF. Bitmasking is performed with mask & (1 << i).
Worked Examples
Example 1
n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]]
Floyd-Warshall distance matrix:
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 0 | 2 | 10 |
| 1 | 2 | 0 | 10 |
| 2 | 10 | 10 | 0 |
Check