Number of Possible Sets of Closing Branches

Number of Possible Sets of Closing Branches

What is this problem about?

The Number of Possible Sets of Closing Branches problem gives you a company with branches (nodes) and roads (edges). You want to close some branches such that the remaining network stays connected and all remaining branches are within a maximum travel distance maxDistance of each other. Count the number of valid subsets of branches that can be closed. This hard coding problem uses bitmask enumeration with all-pairs shortest paths.

Why is this asked in interviews?

Meesho and Atlassian ask this hard problem because with small n (up to ~10), bitmask enumeration over all subsets is feasible, and verifying each subset requires running shortest paths (Floyd-Warshall or Dijkstra). The shortest path, graph, enumeration, heap, and bit manipulation interview pattern is comprehensively tested.

Algorithmic pattern used

Bitmask enumeration + shortest path verification. For each subset of branches to KEEP (complement of closed): use the kept subset to run Floyd-Warshall within that subset. Verify that all pairs in the kept subset have shortest path ≤ maxDistance. Count valid subsets. Total time: O(2^n * n²) — feasible for n ≤ 10-15.

Example explanation

n=3 branches, edges with distances, maxDistance=5.

• Keep all 3: run Floyd-Warshall. If max_pair_distance ≤ 5 → valid.
• Keep subsets of 2: check pair distance ≤ 5 for each.
• Keep 1 or 0: always valid (no pairs to check distance for). Count all valid subsets.

Common mistakes candidates make

• Enumerating subsets to CLOSE instead of to KEEP (equivalent but conceptually cleaner to think about kept subsets).
• Not re-running shortest paths for each subset (must only consider edges between kept nodes).
• Using Dijkstra per pair instead of Floyd-Warshall (less clean for dense small graphs).
• Off-by-one: the empty subset (close all) and single-branch subset are trivially valid.

Interview preparation tip

Bitmask + shortest path is a powerful combination for small-n network optimization. Recognize when n ≤ 15: bitmask over all subsets (2^15 ≈ 32K) with O(n²) verification per subset is feasible. Floyd-Warshall in O(n³) is clean for small dense graphs within each subset. Practice this pattern on "optimal subgraph" problems — they appear in hard graph questions at Atlassian and similar companies.