There is a company with n branches across the country, some of which are connected by roads. Initially, all branches are reachable from each other by traveling some roads.
The company has realized that they are spending an excessive amount of time traveling between their branches. As a result, they have decided to close down some of these branches (possibly none). However, they want to ensure that the remaining branches have a distance of at most maxDistance from each other.
The distance between two branches is the minimum total traveled length needed to reach one branch from another.
You are given integers n, maxDistance, and a 0-indexed 2D array roads, where roads[i] = [ui, vi, wi] represents the undirected road between branches ui and vi with length wi.
Return the number of possible sets of closing branches, so that any branch has a distance of at most maxDistance from any other.
Note that, after closing a branch, the company will no longer have access to any roads connected to it.
Note that, multiple roads are allowed.
Example 1:
Input: n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]] Output: 5 Explanation: 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 Explanation: 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 Explanation: 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 <= 101 <= maxDistance <= 1050 <= roads.length <= 1000roads[i].length == 30 <= ui, vi <= n - 1ui != vi1 <= wi <= 1000Problem Overview: You are given n branches connected by weighted roads. Some branches can be closed. After closing a set of branches, every remaining open branch must still be reachable from every other open branch with a shortest path distance ≤ maxDistance. The task is to count how many subsets of branches can be closed while satisfying this constraint.
Approach 1: Brute Force with Floyd-Warshall Algorithm (Time: O(2^n * n^3), Space: O(n^2))
The simplest approach enumerates every subset of branches using bit manipulation. Each bitmask represents which branches remain open. For a given subset, build a distance matrix for only the active nodes and run the Floyd-Warshall algorithm to compute all-pairs shortest paths. After computing distances, verify that every pair of open branches has a shortest path ≤ maxDistance. If the constraint holds, the subset is valid. This approach works because n is small, making 2^n enumeration feasible. Floyd-Warshall ensures accurate shortest paths across the weighted graph.
Approach 2: Backtracking with DFS and Pruning (Time: O(2^n * n^2) average, Space: O(n^2))
Instead of generating all subsets blindly, use DFS to decide whether each branch stays open or gets closed. While building a configuration, compute shortest distances among currently open nodes and prune early if any pair already exceeds maxDistance. This avoids exploring many invalid states. The pruning step dramatically reduces the search space compared to pure enumeration. Shortest paths can still be evaluated using repeated relaxations or a shortest path routine as nodes are added. The technique blends subset generation with constraint validation.
Recommended for interviews: Start with the brute force subset enumeration combined with Floyd-Warshall. It clearly demonstrates understanding of graph shortest paths and bitmask subset iteration. Once that baseline is established, discuss DFS with pruning to show optimization thinking and control over exponential search spaces.
This approach involves generating all possible subsets of branches that can be closed. For each subset, we consider the remaining branches and check if they satisfy the distance constraint using the Floyd-Warshall algorithm. The Floyd-Warshall algorithm helps to find the shortest paths between all pairs of vertices in a graph, making it straightforward to check the distance condition for every subset.
This Python code breaks down the task into two major parts: calculating all-pairs shortest paths using the Floyd-Warshall algorithm and generating every possible combination of closed branches. For each combination, it checks if the remaining branches (those that are not closed) meet the distance requirement. If they do, the combination is considered valid.
The time complexity of this approach is determined by two factors: the Floyd-Warshall algorithm runs in O(n^3), and generating all subsets of branches runs in O(2^n). Thus, the overall complexity is O(2^n * n^3). The space complexity is mainly O(n^2) due to the distance matrix used in the Floyd-Warshall algorithm.
This approach combines backtracking with a depth-first search (DFS) to explore possible sets of closed branches. It prunes branches of the search tree early when it becomes clear that further exploration cannot lead to a valid set (one where all open branches are within `maxDistance` of each other). This method is more intuitive for graph traversal problems and efficient for small graphs (as n <= 10).
This Java solution utilizes DFS with backtracking to explore possible subsets of closed branches. Each possibility is validated using DFS to ensure that active branches can reach each other within the specified maximum distance. The backtracking process prunes impossible paths early, potentially reducing the time spent exploring useless paths.
Java
JavaScript
Time complexity is O(2^n * n^3) due to the combination of subset generation and Floyd-Warshall's operation, but actual performance is potentially improved by pruning during DFS. Space complexity remains O(n^2) due to distance matrix storage.
We notice that n leq 10, so we might as well consider using the method of binary enumeration to enumerate all subsets of departments.
For each subset of departments, we can use the Floyd algorithm to calculate the shortest distance between the remaining departments, and then judge whether it meets the requirements of the problem. Specifically, we first enumerate the middle point k, then enumerate the starting point i and the ending point j. If g[i][k] + g[k][j] < g[i][j], then we update g[i][j] with the shorter distance g[i][k] + g[k][j].
The time complexity is O(2^n times (n^3 + m)), and the space complexity is O(n^2). Here, n and m are the number of departments and the number of roads, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force with Floyd-Warshall Algorithm | The time complexity of this approach is determined by two factors: the Floyd-Warshall algorithm runs in O(n^3), and generating all subsets of branches runs in O(2^n). Thus, the overall complexity is O(2^n * n^3). The space complexity is mainly O(n^2) due to the distance matrix used in the Floyd-Warshall algorithm. |
| Approach 2: Backtracking with DFS and Pruning | Time complexity is O(2^n * n^3) due to the combination of subset generation and Floyd-Warshall's operation, but actual performance is potentially improved by pruning during DFS. Space complexity remains O(n^2) due to distance matrix storage. |
| Binary Enumeration + Floyd Algorithm | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration with Floyd-Warshall | O(2^n * n^3) | O(n^2) | Small graphs where n ≤ 10 and you need a simple, reliable solution |
| Backtracking with DFS and Pruning | O(2^n * n^2) average | O(n^2) | When many subsets fail early and pruning significantly reduces exploration |
Number of Possible Sets of Closing Branches | Intuition | Leetcode-2959 | Bi-Weekly Contest 119 • codestorywithMIK • 4,255 views views
Watch 6 more video solutions →Practice Number of Possible Sets of Closing Branches with our built-in code editor and test cases.
Practice on FleetCode