Subsets - Backtracking - Leetcode 78

0:00 - Read the problem
1:15 - Drawing explanation
5:30 - Coding explanation

leetcode 78

#subset #permutation #python

[business_central]

For the ppl like me who struggled with grasping the dfs recursive call, below is a simple example:

Let's say we have the list nums = [1, 2, 3] and we call the dfs function with i = 0.

The first call: dfs(0):
The condition i >= len(nums) is false, so we move forward.
nums[0] is appended to subset which is now [1].
A new call is made to dfs(1).

The second call: dfs(1):
The condition i >= len(nums) is false, so we move forward.
nums[1] is appended to subset which is now [1, 2].
A new call is made to dfs(2).

The third call: dfs(2):
The condition i >= len(nums) is false, so we move forward.
nums[2] is appended to subset which is now [1, 2, 3].
A new call is made to dfs(3).

The fourth call: dfs(3):
The condition i >= len(nums) is true, so the current subset [1, 2, 3] is appended to the res list.
The function returns.

The third call returns:
nums[2] is removed from subset which is now [1, 2].
A new call is made to dfs(3).

The fifth call: dfs(3):
The condition i >= len(nums) is true, so the current subset [1, 2] is appended to the res list.
The function returns.

The second call returns:
nums[1] is removed from subset which is now [1].
A new call is made to dfs(2).

The sixth call: dfs(2):
The condition i >= len(nums) is false, so we move forward.
nums[2] is appended to subset which is now [1, 3].
A new call is made to dfs(3).

The seventh call: dfs(3):
The condition i >= len(nums) is true, so the current subset [1, 3] is appended to the res list.
The function returns.

The sixth call returns:
nums[2] is removed from subset which is now [1].
A new call is made to dfs(3).

The eighth call: dfs(3):
The condition i >= len(nums) is true, so the current subset [1] is appended to the res list.

Hope this helps!
And thanks Neetcode for sharing the original solution!

[zoidian]

This is a great video. These backtracking solutions are so hard to understand for some reason. I wish there was an in-depth video about converting general decision trees to these backtracking algorithms

[localstreamers]

Backtracking and choices have always been difficult for me. After watching and understanding your explanations, I am able to solve at problems like subsets, permutations with looking at the code at a all. thanks a lot for your work.

[RichardLopez-lrel]

Just had a coding interview, and this channel helped me so much! Keep up the amazing work!

[radishanim]

I struggled with understanding the reason for appending `subset.copy()` instead of `subset`.
I think what is happening is, we need to append the actual instance of each modified subset `subset.copy()` instead of the reference which is pointing to the subset which gets modified.
Neetcode's stated reason for appending the copy of the subset ("this subset is going to be modified, right?") is correct- the reference will be pointing to a subset that keeps getting modified, which will eventually make the function return a list of empty subsets.



tl:dr; res.append(subset.copy()) actually appends [1, 2, 3] to the res. res.append(subset) appends the pointer to the subset which at the time may be [1, 2, 3] but will eventually be [] due to us popping (aka modifying) the subset.

If this didn't make sense, try adding `print(subset, subset.copy())` at line 7 and `print(res)` at line 9 and 19. That might clarify the situation.

[rustyglen]

Great video! I don't know how you find a way to explain hard problems so clearly. Thanks for uploading these!

[pradgarimella]

Thanks for the amazing explanation. This feels like the 0/1 knapsack problem. There are multiple solutions to this problem, this is the cleanest approach I have seen

[sap]

This is pure gold exactly what I wanted. Thanks for creating this gem

[surajslab]

Your videos are really awesome, the way u explain the problem by splitting it into different section is simply great !!

[rex]

I searched many articles and videos to figure out the problem's time and space complexity. Many of them explain: there are two choices, choose it or not, so the time complexity is O(2^N * N). Only this video draws the recursion tree. I think it helped me realize complexity immediately.

[lhsh]

I was always running away from this question until saw this. Thanks for sharing this video~

[chengjinfei]

I saw a lot ways to solve this issue, but you are the most clean one. Thanks.

[tanmaymokal]

Your videos are so fun to watch and most imp they don't make me sleep.

[noctua]

You're a legend at explaining things simply. Thank you!

[angelocortez]

Had a coding interview recently ; though I didn't pass, with these videos, I definitely feel more confident. I got my first SWE job as an econ major, and have struggled with these concepts even though I took an algorithms class. I definitely feel like your videos taught them better than the professor.

[charanbathula]

about subset.copy(), if we use res.append(subset)--> res is [[subset], [subset]]
so finally when subset is empty[], res will be [[], []]
if we res.append(subset.copy())--> res is [[1], []], used example when nums =[1]

[aditijain]

i just love that all your videos are under 20 mins

[Sportsandgames]

This is great, but I noticed 2 things:

1) I don't think this is backstracking, this is just full recursion DFS. Backtracking is when you pre prune a tree by not going down a certain path with DFS if the partial solution at that level is already wrong (so you backtrack away).

2) line 16, the pop() doesn't represent NOT including it, that wouldn't be an inaccurate way to think about it. What its doing is restoring the state of the slate "subset" to the state it was in before the append inclusion happened. Another way to think about it, is if you switched the code lines for the decisions to include and exclude, you would think you don't need the pop() after calling the DFS on the exclude, when you still do. E.g:

# decision NOT to include nums[i]
DFS(I+1)

# decision to include nums[i]
Subset.append(nums[i])
DFS(i+1)
Subset.pop() # you still need this line here even though you might not think you do

Other than that, this was a great video, thanks!

[elyababakova]

Mindblowing🤯
Thanks for explanation, very helpful!

[KomalPal]

@NeetCode

Seriously thanks a lot, i can only understand recursive problems through recursive tree and thats why it takes me hard to analyse bcoz I have not much people to discuss for the same, srsly thanks a lot for doing the ques the same way it it understandable to me ☺