297. Path of More Than K Length From a Source

Given an undirected weighted graph with n vertices (0-indexed) and m edges, a source vertex, and an integer k, print 'Yes' if there exists a simple path (no vertex repeated) starting at the source whose total edge weight is strictly more than k, otherwise print 'No'.

Input: The first line contains the integer n (vertices). The second line contains the integer m (edges), followed by m lines each with three space-separated integers - the edge's two endpoints and its weight. This is followed by a line with the source vertex and a line with the integer k. Output: Print 'Yes' if a simple path from the source has total weight strictly greater than k, otherwise print 'No'.

1 <= n <= 15, 0 <= m <= n*(n-1)/2, 1 <= edge weight <= 100, 0 <= k <= 10^4

This requires SIMPLE paths (no repeated vertices) - without that constraint, checking for 'any path exceeding weight k' would be trivial (just keep looping around any positive-weight cycle indefinitely), so the visited-set tracking is not optional, it's essential to the problem's meaning.

Check whether there's a simple path (no repeated vertices) starting from a given source whose total edge weight exceeds a given value k. Brute force: Enumerate every possible simple path from the source exhaustively and check each one's total weight - this is what the DFS/backtracking approach effectively does, but checking each fully-explored path's sum rather than stopping the INSTANT the running sum exceeds k during the search itself. Optimised: Checking the running weight sum AS YOU GO (rather than only at the end of a fully-explored path) lets the search stop immediately the moment ANY path segment exceeds k, without needing to explore the rest of that path or any other paths - a significant early-exit optimization over exhaustively completing every path first.

Use DFS/backtracking from the source, exploring every possible simple path (never revisiting a vertex already on the current path) all the way to exhaustion, recording the total weight of every complete simple path found into a list. Once the search finishes, scan the stored list for any path whose weight exceeds k. This does answer the question correctly, but it explores blindly, continuing to enumerate and store every remaining path even after a qualifying one has already been found. Time: O(n!) Space: O(n!)

Run the identical DFS/backtracking exploration of simple paths, but check each path's accumulated weight as it's being built rather than storing every completed path, returning 'Yes' immediately the moment any path's running weight exceeds k and undoing choices (backtracking) instead of retaining full path lists. If the true answer is 'No,' the same exhaustive exploration is still required, but no memory is wasted retaining paths, and successful cases terminate immediately instead of continuing to enumerate everything. Time: O(n!) Space: O(n)

Since n is at most 15, represent visited-vertex sets as bitmasks and define dp[mask][v] as the maximum total weight of a simple path that starts at the source, visits exactly the vertices in mask, and ends at v, computed by extending shorter paths, dp[mask][v] built from dp[mask without v][u] for each neighbor u of v already inside the mask, rather than re-deriving whole paths from scratch each time. The answer is 'Yes' if dp[mask][v] exceeds k for any mask and v combination. This replaces the possibly-factorial backtracking search with one strictly bounded by O(2^n), dramatically smaller than n! once n approaches 15. Time: O(2^n * n^2) Space: O(2^n * n)

1. DFS from the source, tracking the running total weight and a 'visited' set to ensure no vertex is used twice on the current path. 2. The moment the running weight sum exceeds k, stop immediately and answer Yes. 3. Backtrack (unmark the current vertex as visited) when a DFS call returns without success, so other branches can still reuse that vertex on a DIFFERENT path.

Time: O(n!) in the worst case (exploring all possible simple paths), though the small constraint (n<=15) keeps this manageable, and early termination on success often makes it much faster in practice. Space: O(n) for the visited set and recursion stack.

Test m = 0 (no path possible, always 'No'), k = 0 (any single edge from the source suffices), and n = 15 (largest case, since exploring simple paths is exponential).

Be ready to explain WHY this needs backtracking (unmarking visited vertices) rather than a standard single-pass DFS - since the SAME vertex might be usable on multiple different candidate paths from the source, marking it visited must be undone once a particular branch's exploration is complete.