Problem

This problem is asked at so: I have a network of stations in a subway system. The number of stations, the number of tickets I can travel between stations with, and which stations are connected to each other are given in a text file as input to the program. Which stations are connected to each other are kept in a 2D boolean matrix. I have to find the number of paths from station 0 and back to 0 that uses all of the tickets.

OR

Given a graph (as an adjacency matrix), count the number of roundtrip paths of exactly k steps that start and end at the origin node (node 0).

Examples

Example 1

graph TD;
  A(0) --- B(1) & E(4)
  B --- F(5) & C(2) & G(6)
  F --- D(3)
  C --- D
  G --- D
  E --- D

Adjacency matrix of the graph:

$$ \begin{array}{|c|ccccccc|} \hline & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 2 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 3 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 4 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 5 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 6 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ \hline \end{array} $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

Input:
adj = [
     [0, 1, 0, 0, 1, 0, 0],
     [1, 0, 1, 0, 0, 1, 1],
     [0, 1, 0, 1, 0, 0, 0],
     [0, 0, 1, 0, 1, 1, 1],
     [1, 0, 0, 1, 0, 0, 0],
     [0, 1, 0, 1, 0, 0, 0],
     [0, 1, 0, 1, 0, 0, 0]
],
k = 5
Output: 6
Explanation: Starting and returning to 0, there are 6 roundtrip paths of length 5:
0-1-2-3-4-0
0-1-5-3-4-0
0-1-6-3-4-0
0-4-3-6-1-0
0-4-3-5-1-0
0-4-3-2-1-0

Solution

Method 1 – Top-Down Dynamic Programming (Memoized Recursion)

Intuition

Use recursion with memoization to count the number of ways to return to node 0 in exactly k steps. At each step, try all possible next nodes, and cache results to avoid recomputation.

Approach

  1. Define a function f(u, t) = number of ways to reach node 0 from node u in t steps.
  2. Base case: if t == 0, return 1 if u == 0, else 0.
  3. For each neighbor v of u, recursively compute f(v, t-1) and sum the results.
  4. Use memoization to cache results for (u, t).
  5. The answer is f(0, k).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <vector>
#include <cstring>
using namespace std;
class Solution {
public:
  int countRoundtripPaths(const vector<vector<int>>& adj, int k) {
    int n = adj.size();
    vector<vector<int>> memo(n, vector<int>(k+1, -1));
    function<int(int,int)> dp = [&](int u, int t) {
      if (t == 0) return u == 0 ? 1 : 0;
      if (memo[u][t] != -1) return memo[u][t];
      int res = 0;
      for (int v = 0; v < n; ++v) if (adj[u][v]) res += dp(v, t-1);
      return memo[u][t] = res;
    };
    return dp(0, k);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.*;
class Solution {
  public int countRoundtripPaths(int[][] adj, int k) {
    int n = adj.length;
    Integer[][] memo = new Integer[n][k+1];
    return dp(0, k, adj, memo);
  }
  private int dp(int u, int t, int[][] adj, Integer[][] memo) {
    if (t == 0) return u == 0 ? 1 : 0;
    if (memo[u][t] != null) return memo[u][t];
    int res = 0;
    for (int v = 0; v < adj.length; ++v) if (adj[u][v] == 1) res += dp(v, t-1, adj, memo);
    return memo[u][t] = res;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
  def count_roundtrip_paths(self, adj: list[list[int]], k: int) -> int:
    from functools import lru_cache
    n = len(adj)
    @lru_cache(maxsize=None)
    def dp(u, t):
      if t == 0:
        return 1 if u == 0 else 0
      res = 0
      for v in range(n):
        if adj[u][v]:
          res += dp(v, t-1)
      return res
    return dp(0, k)

Complexity

  • ⏰ Time complexity: O(kN^2), where k is the number of steps and N is the number of nodes. Each state (u, t) is computed once, and for each, we try all N neighbors.
  • 🧺 Space complexity: O(kN), for the memoization table.

Method 2 – Bottom-Up Dynamic Programming

Intuition

Use dynamic programming to count the number of ways to reach each node in exactly t steps, building up from 0 to k steps. The answer is the number of ways to return to the origin node in k steps.

Approach

  1. Let dp[t][u] be the number of ways to reach node u in t steps.
  2. Initialize dp[0][0] = 1 (start at node 0 with 0 steps).
  3. For each step t from 1 to k:
  • For each node s, if dp[t-1][s] > 0, for each neighbor adj of s:
    • Add dp[t-1][s] to dp[t][adj] if there is an edge from s to adj.
  1. The answer is dp[k][0] (number of ways to return to node 0 in k steps).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
  int countRoundtripPaths(const vector<vector<int>>& adj, int k) {
    int n = adj.size();
    vector<vector<int>> dp(k + 1, vector<int>(n, 0));
    dp[0][0] = 1;
    for (int t = 1; t <= k; ++t) {
      for (int s = 0; s < n; ++s) {
        if (dp[t-1][s] == 0) continue;
        for (int adjNode = 0; adjNode < n; ++adjNode) {
          if (adj[s][adjNode]) {
            dp[t][adjNode] += dp[t-1][s];
          }
        }
      }
    }
    return dp[k][0];
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
  public int countRoundtripPaths(int[][] adj, int k) {
    int n = adj.length;
    int[][] dp = new int[k + 1][n];
    dp[0][0] = 1;
    for (int t = 1; t <= k; t++) {
      for (int s = 0; s < n; s++) {
        if (dp[t-1][s] == 0) continue;
        for (int adjNode = 0; adjNode < n; adjNode++) {
          if (adj[s][adjNode] == 1) {
            dp[t][adjNode] += dp[t-1][s];
          }
        }
      }
    }
    return dp[k][0];
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
  def count_roundtrip_paths(self, adj: list[list[int]], k: int) -> int:
    n = len(adj)
    dp = [[0] * n for _ in range(k + 1)]
    dp[0][0] = 1
    for t in range(1, k + 1):
      for s in range(n):
        if dp[t-1][s] == 0:
          continue
        for adj_node in range(n):
          if adj[s][adj_node]:
            dp[t][adj_node] += dp[t-1][s]
    return dp[k][0]

Complexity

  • ⏰ Time complexity: O(kN^2), where k is the number of steps and N is the number of nodes. Each step considers all pairs of nodes.
  • 🧺 Space complexity: O(kN), for the DP table.