Watch 7 video solutions for Number of Possible Sets of Closing Branches, a hard level problem involving Bit Manipulation, Graph, Heap (Priority Queue). This walkthrough by codestorywithMIK has 4,255 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |