-2
$\begingroup$

I'm trying to solve the following Leetcode problem: https://leetcode.com/problems/path-sum-ii/description/

This solution I came up with is working: https://pastebin.com/ma3DtU5b

However, I was not happy with passing vector currentPath by value in my dfs function because of it uses too much memory by creating a new vector for each dfs function call.

So I modified the dfs function to pass vector currentPath by reference and added a backtracking instruction at line 9 here: https://pastebin.com/Kvn8CfwB

However this solution is not working and doesn't pass Leetcode test cases.

I read the Editorial solution for this problem and it looks very similar to my non-working one, except that it passes a remainingSum instead of a currentSum to the dfs function calls.

Please help me understand the difference and what's wrong in my solution, I tried to understand by myself and with the help of a LLM but I couldn't.

Improve this question
New contributor
Platus is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

The issue lies in line 23 in the plain return after you reach leaf and return from the recursion before popping the element.

You either fix this by adding currentPath.pop_back() before the return or by erasing the return on line 23 completely. Note that since left and right are nullptrs, the next call to dfs will terminate on the first if-condition.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.