mediumBacktrackingPattern: Backtracking
Find All Paths with Bounded Sum Solution
Problem Statement
Given a directed acyclic graph (DAG) represented by an adjacency list `graph` and an array `edgeWeights` where `graph[i]` contains a list of nodes adjacent to node `i`, and `edgeWeights[i][j]` represents the weight of the edge from node `i` to `graph[i][j]`. Also given is a maximum path sum `maxSum`. Find all distinct paths from a source node `startNode` to a target node `endNode` such that the sum of edge weights along each path does not exceed `maxSum`. Each node can be visited at most once within a single path.
Examples
Example 1:
Input:graph = [[1, 2], [3], [3], []], edgeWeights = [[5, 3], [7], [2], []], startNode = 0, endNode = 3, maxSum = 15
Output:[]
Explanation: Path 0 -> 1 -> 3 has a sum of 5 + 7 = 12, which is <= 15. Path 0 -> 2 -> 3 has a sum of 3 + 2 = 5, which is <= 15. Both paths are valid.
Example 2:
Input:graph = [[1], [2], [3], []], edgeWeights = [[10], [10], [10], []], startNode = 0, endNode = 3, maxSum = 25
Output:[]
Explanation: The only path is 0 -> 1 -> 2 -> 3 with a sum of 10 + 10 + 10 = 30, which exceeds the maxSum of 25. Therefore, no valid paths exist.
Example 3:
Input:graph = [[1, 2], [3], [3], []], edgeWeights = [[5, 3], [7], [2], []], startNode = 0, endNode = 3, maxSum = 7
Output:[]
Explanation: Path 0 -> 1 -> 3 has a sum of 5 + 7 = 12, which exceeds maxSum = 7. Path 0 -> 2 -> 3 has a sum of 3 + 2 = 5, which is <= 7. Only path 0 -> 2 -> 3 is valid. The original provided output was [[0, 2, 3]], which is correct for this input. My previous evaluation was incorrect regarding the sum of path 0->1->3.
Constraints
- The number of nodes `n` is between 1 and 100.
- The number of edges `m` is between 0 and `n*(n-1)/2`.
- Edge weights are integers between 1 and 1000.
- The `maxSum` is an integer between 0 and 100000.
- The graph is guaranteed to be a Directed Acyclic Graph (DAG).
Time: O(V + E * 2^V) in the worst case, where V is the number of vertices and E is the number of edges. In a DAG, it's closer to O(V + E) if paths are short, but can degrade if many paths exist within the sum limit. Space: O(V) for the recursion stack and storing the current path, plus O(P*V) where P is the number of valid paths.
Utilize a Depth-First Search (DFS) algorithm. Start a DFS from the `startNode`. Maintain the current path and its accumulated weight. When traversing an edge, add the edge weight to the current sum and the destination node to the path. If the current sum exceeds `maxSum` or a node is revisited in the current path, backtrack. If the `endNode` is reached and the sum is within the `maxSum`, record the current path.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def find_all_paths_with_bounded_sum(graph, edge_weights, start_node, end_node, max_sum):
paths = []
n = len(graph)
def dfs(current_node, current_path, current_sum, visited_in_path):
current_path.append(current_node)
visited_in_path.add(current_node)
if current_node == end_node:
if current_sum <= max_sum:
paths.append(list(current_path))
current_path.pop()
visited_in_path.remove(current_node)
return
if current_sum > max_sum:
current_path.pop()
visited_in_path.remove(current_node)
return
neighbors = graph[current_node]
weights = edge_weights[current_node]
for i in range(len(neighbors)):
neighbor = neighbors[i]
weight = weights[i]
if neighbor not in visited_in_path:
dfs(neighbor, current_path, current_sum + weight, visited_in_path)
current_path.pop()
visited_in_path.remove(current_node)
# Handle the edge case where startNode equals endNode
if start_node == end_node:
if max_sum >= 0:
return [[start_node]]
else:
return []
dfs(start_node, [], 0, set())
return paths