Problem statement

A company has n branches numbered 0 to n - 1, linked by two-way roads: roads[i] = [u, v, w] is a road of length w between branches u and v. There may be several roads between the same two branches.

The company wants to close some set of branches (possibly none, possibly all). After closing, the branches still open must all be within maxDistance of each other, travelling only through open branches. Closed branches and the roads touching them can no longer be used.

Return the number of possible sets of branches to close such that every pair of open branches is at distance at most maxDistance.

Example 1

Input: n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]]
Output: 5
Explanation: Valid closings: {0,1,2} (nothing open), {0,1} and {1,2} and {0,2} (one branch open), and {2} (0 and 1 open, 2 apart). Keeping 2 open with another branch puts them 10 apart.

Example 2

Input: n = 3, maxDistance = 5, roads = [[0,1,20],[0,1,10],[1,2,2],[0,2,2]]
Output: 7
Explanation: Every closing works except closing only {2}: then 0 and 1 are 10 apart.

Example 3

Input: n = 1, maxDistance = 10, roads = []
Output: 2
Explanation: Close the only branch, or keep it open.

Constraints

• 1 <= n <= 10
• 1 <= maxDistance <= 10^5
• 0 <= roads.length <= 1000
• roads[i].length == 3
• 0 <= u, v <= n - 1
• u != v
• 1 <= w <= 1000
• all branches are reachable from each other when every road is used

Hints for Number of Possible Sets of Closing Branches

1. Hint 1

   With at most 10 branches there are at most 2^10 = 1024 choices of which branches stay open — try them all.

2. Hint 2

   For one choice, you need shortest distances between open branches using only roads whose both ends are open. Floyd–Warshall over the open branches is short and fast enough.

3. Hint 3

   Keep only the cheapest road between each pair, and count the choice when every pair of open branches ends up within maxDistance (an empty or single-branch choice always counts).

How to solve Number of Possible Sets of Closing Branches

The number of branches is tiny, so enumerate every subset of open branches as a bitmask. For each subset, all-pairs shortest paths restricted to the open branches decide whether it is valid.

Approach

1. Build w[u][v], the cheapest road between u and v (infinity if none).
2. For each mask from 0 to 2^n − 1: copy w restricted to the open branches into d, with d[i][i] = 0.
3. Run Floyd–Warshall over the open branches only.
4. If every pair of open branches has d[i][j] <= maxDistance, count the mask.

Why it works

Closing a branch removes it and its roads, so the distances that matter are shortest paths in the subgraph induced by the open branches — exactly what the restricted Floyd–Warshall computes. Enumerating all masks covers every possible set of closed branches once.

Complexity

• Time — O(2^n · n^3)
• Space — O(n^2)

Pitfalls

• Multiple roads can join the same pair; keep the shortest.
• Paths may not pass through closed branches — restrict the intermediate node in Floyd–Warshall too.
• Disconnected open branches have infinite distance and make the mask invalid; the empty mask and every single-branch mask are always valid.

Reference solution

Python

from typing import List

def numberOfSets(n: int, maxDistance: int, roads: List[List[int]]) -> int:
    INF = float("inf")
    w = [[INF] * n for _ in range(n)]
    for u, v, c in roads:
        if c < w[u][v]:
            w[u][v] = w[v][u] = c
    count = 0
    for mask in range(1 << n):
        nodes = [i for i in range(n) if mask >> i & 1]
        d = [row[:] for row in w]
        for i in nodes:
            d[i][i] = 0
        for k in nodes:
            dk = d[k]
            for i in nodes:
                di = d[i]
                dik = di[k]
                if dik == INF:
                    continue
                for j in nodes:
                    if dik + dk[j] < di[j]:
                        di[j] = dik + dk[j]
        if all(d[i][j] <= maxDistance for i in nodes for j in nodes):
            count += 1
    return count

Java

public static int numberOfSets(int n, int maxDistance, int[][] roads) {
    final int INF = 1000000000;
    int[][] w = new int[n][n];
    for (int[] row : w) Arrays.fill(row, INF);
    for (int[] r : roads) if (r[2] < w[r[0]][r[1]]) { w[r[0]][r[1]] = r[2]; w[r[1]][r[0]] = r[2]; }
    int count = 0;
    int[][] d = new int[n][n];
    int[] nodes = new int[n];
    for (int mask = 0; mask < (1 << n); mask++) {
        int m = 0;
        for (int b = 0; b < n; b++) if (((mask >> b) & 1) == 1) nodes[m++] = b;
        for (int x = 0; x < n; x++) for (int y = 0; y < n; y++) d[x][y] = x == y ? 0 : w[x][y];
        for (int p = 0; p < m; p++) {
            int k = nodes[p];
            for (int q = 0; q < m; q++) {
                int s = nodes[q];
                if (d[s][k] == INF) continue;
                for (int t = 0; t < m; t++) {
                    int e = nodes[t];
                    if (d[s][k] + d[k][e] < d[s][e]) d[s][e] = d[s][k] + d[k][e];
                }
            }
        }
        boolean ok = true;
        for (int f = 0; f < m && ok; f++)
            for (int g = 0; g < m; g++)
                if (d[nodes[f]][nodes[g]] > maxDistance) { ok = false; break; }
        if (ok) count++;
    }
    return count;
}

C++

int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
    const int INF = 1000000000;
    vector<vector<int>> w(n, vector<int>(n, INF)), d(n, vector<int>(n));
    for (auto& r : roads) if (r[2] < w[r[0]][r[1]]) { w[r[0]][r[1]] = r[2]; w[r[1]][r[0]] = r[2]; }
    int count = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> nodes;
        for (int b = 0; b < n; b++) if ((mask >> b) & 1) nodes.push_back(b);
        for (int x = 0; x < n; x++) for (int y = 0; y < n; y++) d[x][y] = x == y ? 0 : w[x][y];
        for (int k : nodes)
            for (int s : nodes) {
                if (d[s][k] == INF) continue;
                for (int e : nodes)
                    if (d[s][k] + d[k][e] < d[s][e]) d[s][e] = d[s][k] + d[k][e];
            }
        bool ok = true;
        for (int f : nodes) {
            for (int g : nodes) if (d[f][g] > maxDistance) { ok = false; break; }
            if (!ok) break;
        }
        if (ok) count++;
    }
    return count;
}

JavaScript

var numberOfSets = function(n, maxDistance, roads) {
    var INF = 1000000000;
    var w = [];
    for (var i = 0; i < n; i++) { w.push([]); for (var j = 0; j < n; j++) w[i].push(INF); }
    for (var r = 0; r < roads.length; r++) {
        var u = roads[r][0], v = roads[r][1], c = roads[r][2];
        if (c < w[u][v]) { w[u][v] = c; w[v][u] = c; }
    }
    var count = 0;
    var d = [];
    for (var a = 0; a < n; a++) d.push(new Array(n));
    for (var mask = 0; mask < (1 << n); mask++) {
        var nodes = [];
        for (var b = 0; b < n; b++) if ((mask >> b) & 1) nodes.push(b);
        for (var x = 0; x < n; x++) for (var y = 0; y < n; y++) d[x][y] = x === y ? 0 : w[x][y];
        for (var p = 0; p < nodes.length; p++) {
            var k = nodes[p];
            for (var q = 0; q < nodes.length; q++) {
                var s = nodes[q];
                if (d[s][k] === INF) continue;
                for (var t = 0; t < nodes.length; t++) {
                    var e = nodes[t];
                    if (d[s][k] + d[k][e] < d[s][e]) d[s][e] = d[s][k] + d[k][e];
                }
            }
        }
        var ok = true;
        for (var f = 0; f < nodes.length && ok; f++)
            for (var g = 0; g < nodes.length; g++)
                if (d[nodes[f]][nodes[g]] > maxDistance) { ok = false; break; }
        if (ok) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More bit manipulation problems

• Minimum Score After Removals on a Tree Hard
• Minimum Number of Flips to Convert Binary Matrix to Zero Matrix Hard
• Find the Maximum Sequence Value of Array Hard
• Select Cells in Grid With Maximum Score Hard
• Minimum Sum of Values by Dividing Array Hard
• Maximize the Number of Partitions After Operations Hard