Subsets - Backtracking - Leetcode 78
Vložit
- čas přidán 29. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: neetcode.io/problems/subsets
0:00 - Read the problem
1:15 - Drawing explanation
5:30 - Coding explanation
leetcode 78
This question was identified as an Apple interview question from here: github.com/xizhengszhang/Leet...
#subset #permutation #python - Věda a technologie
💡 BACKTRACKING PLAYLIST: czcams.com/video/pfiQ_PS1g8E/video.html
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!
Thank you for the explanation! It's really helpful :)
Can I ask after the dfs(3), where condition i >= len(nums) is true, how does it know to return to dfs(2)?
Shouldn't the code dfs(i-1) be added after return?
Original code:
def dfs(i):
if i >= len(nums):
res.append(subset.copy())
return
subset.append(nums[i])
dfs(i + 1)
subset.pop()
dfs(i + 1)
@@gggeeh Let's consider the example of the dfs function in the given code. When the function is first called with dfs(0), a new instance of the function is added to the call stack. This instance starts executing and calls dfs(1), which in turn calls dfs(2), and so on.
When the innermost call to dfs(3) returns, it pops off the call stack, and the control returns to the previous instance of the function, which was waiting for the call to return. The previous instance then continues executing from where it left off, which is the next line of code after the recursive call that just returned.
In the example you asked about, after the call to dfs(3) returns, the control is returned to the previous instance of the dfs function, which was dfs(2). The code then continues executing from where it left off in the dfs(2) call, which is the next line of code after the dfs(3) call, which is subset.pop(). This line removes the last element from the subset list, and then the code continues with the next line, which is the next recursive call to dfs(3).
mind blowing! Thx
what about [2], [2,3] and []?
Really helpful. Great work !!
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
Its hard but if u just take an example and run through his function u will get to know what exactly is happening
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.
Nice explanation..an easy way to demonstrate that is:
list1 = [1, 2]
list2 = []
list2.append(list1)
list1.pop()
print(list1) #prints [1]
print(list2) #prints [[1]]
Thank you for this explanation, this makes sense
Thanks for the explaination! I didn't get it before! :)
If you know how to debug python files, you can replace subset.copy() with subset and use VSCode (or any IDE) to run the debugger and see the res being changed with respect to subset because it's a reference to it.
Thanks, buddy!
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.
Just had a coding interview, and this channel helped me so much! Keep up the amazing work!
Great video! I don't know how you find a way to explain hard problems so clearly. Thanks for uploading these!
This is pure gold exactly what I wanted. Thanks for creating this gem
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
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!
i totally second your opinon, and i don't know why are people call it backtracking :D, i thought i was only the one who has this opinion
Great thanks for the explanation!!!
Can you share the backtracking solution then?
great inspiration
For your second point, I disagree. Surely you will need pop() no matter what because you need to explore the different combinations for the subset, but intuitively you can still consider pop() as excluding elements. Hence why the total count of subsets is 2^N, because at each element we have 2 choices (include or don't). For instance, at the beginning of the algorithm we have 2 choices for the set [1, 2, 3], either include [1] in the subset or do not.
When the leaf nodes of the entire left subtree of the root are explored and control returns to our first function call this is what it looks like:
index = 0
subset = [1]
createSubset([1], 0 + 1)
subset = []
createSubset([], 0 + 1) // Now explore all subsets without 1
So essentially we have used pop() to now to exclude 1, and begin to explore all subsets that do not contain 1. What you call "restoring state" is the exclusion of the element we added to allow us to explore the branch of the tree that does not contain that element.
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.
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]
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.
I took some CS courses at a good university and for certain Neetcode explains these concepts much better than the tenured professors and their TAs with many years of programming experience.
Your videos are really awesome, the way u explain the problem by splitting it into different section is simply great !!
I was always running away from this question until saw this. Thanks for sharing this video~
It looks like there is much simpler solution:
def subsets(nums: List[int]) -> List[List[int]]:
subs = [[]]
for n in nums:
for i in range(len(subs)):
subs.append(subs[i] + [n])
return subs
This is how I did it. Much easier!
I saw a lot ways to solve this issue, but you are the most clean one. Thanks.
Your videos are so fun to watch and most imp they don't make me sleep.
I used DP the same way as you used for Partition Equal Subset Sum.
Code:
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res=[[]]
for i in nums:
new=[]
for t in res:
new.append(t)
new.append(t+[i])
res=new
return res
Btw love your videos.
yeah, I have a similar one, you don't even have to overwrite your results everytime:
subsets = [[]]
for n in nums:
for i in range(len(subsets)):
subsets += [subsets[i]+[n]]
return subsets
Combining every new element with all existing subsets feels just so much more natural and easier to understand.
Who said that the input array has no duplicates? If that's true the solutions here are okay.
@@ma_sundermeyer This seems like a much more intuitive solution to me, I came up with something very similar. Yours is very elegant. Good job!
You're a legend at explaining things simply. Thank you!
Easy solution using list.extend() and list comprehension:
res = [[]]
for num in nums:
res.extend([item + [num] for item in res])
return res
i just love that all your videos are under 20 mins
How does the index value keep changing during recursion? I was debugging it and I noticed how the "i" value changes but did not understand how.
wow 300 times better than other videos/leetcode solutions
Mindblowing🤯
Thanks for explanation, very helpful!
@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 ☺
Thank you, It was well-explained and neat!
could you tell us what tool do you use to draw the graphs?
The tree is really helpful! Cheers
Thanks for your contribution. Cheers!
Can someone explain me why we need to add the copy of subset there??
Great explanation. Thank you
I love you man. keep up the great work !
your code is super clean
Great explanation!
Amazing video superb explnation..please make a video on subset2 also..
for all people struggling with recursive code I assure you most of us have been in same situation initially but as you practice more problems (wont take too long if u r consistent) I assure that you will be surprised how naturally it comes to you
reading this was really helpful. understanding recursion has been a nightmare for me. hopefully I get better by solving more problems
Best explanation ever！
great video, ty
Pls show the inner implementation of this code using stack I couldn't able to understand what is happening after poping out the element
For people who are wondering why to use nums.copy() :
Because the list nums is being modified during the function calls. If you just append it to the output you append a reference (pointer) to nums not the actual list which means that after nums is modified from some other recursive function it will be "changed" in the output list that stores the reference to nums. In the end, output will contain pointers that will point to the same result (whatever was the last change in nums). So you need to make a deep copy of nums.
Note: If I'm not mistaken you can use nums[:] instead of nums.copy(), so we can still stay w/ Python2 instead of Python3..
BRO, I was struggling with this question earlier when it kept appending new subsets to existing list, and was forced to watch this video as a result. After i found your comment and added .copy() to the working list that I pass to new dfs() calls, IT WORKED LIKE A CHARM. THANKS
@@meowmaple u can use nums[:] as well
Uh, there is no nums.copy() in the entire video...
If you mean subset.copy() then your explanation makes no sense because subset is not modified once the base case (i >= len(nums)) is met.
@@Zeegoner I struggled with understanding the reason for appending `subset.copy()` instead of `subset` for a couple of hours as well.
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, I think adding `print(subset, subset.copy())` at line 7 and `print(res)` at line 9 and 19 might clarify the situation.
we can also do this with bitwise manipulation where we will run a for loop from 0 to 2^n that is the no of subsets.
Hey can you explain the how time complexity is O(n * 2^n) ??
Since the recursion is kind of working as a complete binary tree, should not it be O(2^(n+1))
probably due to the copy() operation
If it’s going to be O(n*2^n) anyway, loop i from 0 to 2^n-1 and divide i by 2 n times to decide which element to be included. You don’t need backtracking at all
Simpler solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
output = []
def dfs(i, path):
output.append(path[:])
for j in range(i, len(nums)):
path.append(nums[j])
dfs(j + 1, path)
path.pop()
dfs(0, [])
return output
The method for coding it up seems overly complicated. This solution on Leetcode helped me understand the problem much better.
def generateSubset(nums):
if not nums:
return [[]]
tail = generateSubset(nums[1:])
currentValue = nums[0]
output = []
for subset in tail:
output.append(subset)
output.append([currentValue] + subset)
return output
return generateSubset(nums)
What is the run time of the solution? Is this O(n^2)?
Damn, the tree was exact how the recursion stack will create during recursion. But the only disconnect I felt was he explained how the tree is created from top to bottom, but during the program execution, the tree is created from bottom to top. It took me some time to wrap my head around it.
Thank you very much
Hello Neat Code!
Your work is amazing and really helpful!
Can you please elaborate about the Time and Space complexities?
Thank you very much
Neet** sorry! :D
Hey appreciate the kind words!
For Time it is O(n * 2^n) because there will be 2^n different subsets, and we have to create a copy of each one, which is O(n).
For Space it is O(n) if you don't count the output array, because the size of the function call stack will be O(n). Meaning we have to call the recursive function n times in a row, before it returns.
@@NeetCode Ah now it's clear, great! thank you!!
@@NeetCode that means, if there is no copying then it is O(2^n)
CLEANNNN SOLUTION!
thanks , man !
you don't need to add and then pop, you can just do dfs() and then do append + dfs(), which makes things more effecient. Also the >= comparison doesn't make sense, since you can't go over len(nums) so i == len(nums) if sufficient.
Why doesn't this terminate right away, since subset starts with len 0 and the first thing we check is if i is greater than or equal to subset, with i = 0?
As in, i = 0, and len(subset) = 0, so why do we not terminate first thing?
Here what happens with subset during backtracking, which might help to understand it.
append to subset [1] 0
append to subset [1, 2] 1
append to subset [1, 2, 3] 2
add to res: [1, 2, 3] 3
pop from subset [1, 2, 3] 2
add to res: [1, 2] 3
pop from subset [1, 2] 1
append to subset [1, 3] 2
add to res: [1, 3] 3
pop from subset [1, 3] 2
add to res: [1] 3
pop from subset [1] 0
append to subset [2] 1
append to subset [2, 3] 2
add to res: [2, 3] 3
pop from subset [2, 3] 2
add to res: [2] 3
pop from subset [2] 1
append to subset [3] 2
add to res: [3] 3
pop from subset [3] 2
add to res: [] 3
BFS
def subsets(self, nums: List[int]) -> List[List[int]]:
result = [[]]
q = deque()
for i, num in enumerate(nums):
q.append((i, [num]))
while q:
i, array = q.popleft()
result.append(array)
for j in range(i+1, len(nums)):
q.append((j, array + [nums[j]]))
return result
This solution is more intuitive to me than the for loop one! Exactly what i thought. Is it posisble to do a video on subset II (subset with duplicate) on top of this approach please? Looking forward to it!
I feel the same....
can also just jsut an iterative solution:
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
# backtracking
# time: O(n*2^n)
# space: O(2^n)
output = []
# base case
output.append([])
# constraint: add n nums
for num in nums:
# choice: do or don't add the number to the list
for i in range(len(output)):
# don't add the number by appending the list with the current list
output.append(output[i])
# add the number to the current list
output[i] = output[i] + [num]
return output
Could you please do Subsets - ii (Leetcode 90) as well?
Thanks
U a God
Here's my implementation without the need for subset.copy(), you'll just have to pass in the subset directly in the parameter as you create the subset recursively:
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
def dfs(i,curr): # pass in the current idx and the current subset
if i >= len(nums): # base case
res.append(curr) # add the subset
return
dfs(i+1,curr+[nums[i]]) # to include nums[i]
dfs(i+1,curr) # not to include nums[i]
dfs(0,[]) # start at index 0 and with empty list
return res
Backtracking with choices...great!!
Hey guys, I'm a bit confused why this is classified as backtracking and not just regular recursion. We don't ever really hit a constrained choice and have to backtrack?
yeah same qs
Can anyone explain why we are using subset.copy() and why without it the output is an array with empty subsets??
Because lists are mutable data types in Python.
Thanks!
Sir, I understand your code after your explanation. But when I use js to write out a successful code as yours in Python, I tried to visualize it by using debugger in vs code. I want to know how exactly the code runs. However, I'm totally lost, the "return" in the base case is where the i index decreases. Could you elaborate more on how the index changes so irregularly? The subset array length seems to have null influence on the change of the i index.
debugger;
var subsets = function (nums) {
let res = [],
subset = [];
const dfs = i => {
if (i === nums.length) {
res.push(subset.slice());
return;
}
subset.push(nums[i]);
dfs(i + 1);
subset.pop();
dfs(i + 1);
};
dfs(0);
return res;
};
console.log(subsets([1, 2, 3]));
amazing. thanks
I have a concern. Isn't the time complexity like this, 2^(n+1) - 1, n = len(nums), ?
Easier to understand:
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
subs = []
sub = []
def solve(i):
subs.append(sub.copy())
for j in range(i,len(nums)):
sub.append(nums[j])
solve(j + 1)
sub.pop()
solve(0)
return subs
Very nice video.....
Appreciate it.
backtracking question is the most difficult question to me. Where can I learn it and improve my skill with backtracking?
Another two solution, slightly different, but very intuitive to beginner for understanding backtracking.
# control for loop to end dfs func. so no need to add edge case
# res, sub = [], []
# def dfs(i):
# res.append(sub.copy())
# for j in range(i, len(nums)):
# sub.append(nums[j])
# dfs(j + 1)
# sub.pop()
# dfs(0)
# return res
res = []
def dfs(i, sub):
res.append(sub)
for j in range(i, len(nums)):
dfs(j + 1, sub + [nums[j]])
dfs(0, [])
return res
I actually think the time complexity is O(n^2 + 2^n), can someone criticize my logic?
- the number of subset is 2^n, but the number of nodes in the binary decision tree is actually 2^(n+1) - 1. So time complexity to go through all nodes is O(2^(n+1) - 1), which simplifies to O(2^n).
- at each leaf node (and there are (n + 1) / 2 leaf nodes in the tree), a copy of the subset is made. So time complexity here is (n+1)/2*n = O(n^2)
- so final time complexity is O(n^2 + 2^n) , which can possibly reduced to O(2^n)?
At 2:25, why is it big o of( n * 2^n)? If it has 2^n sets aka powerset then shouldnt the big o be just big o of(2^n)? Where did the n come from?
for ever index you are making 2 recursive calls. so time complexity for generating subsets is O(2^N). then you need to copy each subset to the res. How long does it take for each? Copying operation is related to the size of the subset, and worst case is when subset has n elements. So copying takes n
@@veliea5160 You explained better than the video. In the video, the time complexity was given too early before the code was written. It's easier to see where the N comes from after seeing the code.
@@veliea5160 Thank you so much, literally looking for this comment
@@veliea5160 oh man, this exactly what I m looking for after browsing the comments. Please upvote this
Can some one tell me why deep copy was not used?
thanks
Learned a lot, thanks! Also the TC can be improved to n^2 (n=length of input array) using Bit Manipulation.
this is still n^2, because you should use bits as input not integers
is the time complexity of this recursive algo O(2^n) or O(n*2^n)? I know neetcode says n*2^n, but several articles suggest it is 2^n. Several articles suggest it is n*2^n, I really have no idea lol. We know we have a total of 2^n solutions. Why is it times n?
i dont know why also did u know why??
Can someone explain, when does subset.pop( ) line get executed?
It's when we want to do the right decision to add nothing (so revert our previous decision). In other words it's like doing root.right, but because we are just imitating a tree structure and we don;t actually have a root we are doing subset.pop()
good video
Liked and Subscribed :)
Can you post 1 for subset 2?
sorting is used to because element can be more than once. then set is used effectively.
ans=set()
temp=[]
def dfs(index):
if index==len(nums):
ans.add(tuple(temp))
return
temp.append(nums[index])
dfs(index+1)
temp.pop()
dfs(index+1)
nums.sort()
dfs(0)
return ans
@@ritikjain307 converting to sets with the tuple method makes this so simple! Thank you!
Why the time complexity is O(N*2^N) and not just O(2^N)? Can anyone please help?
I think he's saying it's n*2^n because the total number of subsets is 2^n and then for each one of those he has to run the copy() function, which worst case is O(N) time.
there is mistake, or i made a mistake. i think...
# decision to include nums[i]
subset.append(nums[i])
dfs(i+1)
subset.pop() #pop() is for backtracking reason. it has to remove the old element from the subset before traversing a new path
# decision NOT to include nums[i]
dfs(i+1) # this is mean give a empty result, it doesn't do anything to subset.
I think we can also do this recursively.
What is the complexity for this solution ? Time and Space
i want to share my solution with u guys, i think this one is more syntactic sugar for me even if it uses the same algo,
(ts solution)
function subsets(nums: number[]): number[][] {
return calc(0, nums, []);
};
function calc(index: number, nums: number[], curr:number[] ) {
if (index >= nums.length) return [curr];
let withx = calc(index + 1, nums, [...curr, nums[index]]);
let withoutx = calc(index + 1, nums, curr);
return [...withx, ...withoutx]
}
Can you post the solution for subset II using your method? I know it involves sorting nums first and comparing `num[i] == nums[i-1]`, but I still not solve all the test cases
Sure I'll try to solve it soon
why does doing the following lead to an incorrect solution?
dfs(i + 1)
subset.append(nums[i])
dfs(i+1)
you did:
subset.append(nums[i])
dfs(i+1)
subset.pop()
dfs(i+1)
my logic with the first one is that you don't include nums[i] in the first dfs call but you do include it in the second one when you append nums[i] to subset. Evidently, my logic is wrong, an explanation would be appreciated.
i see what I misundestood. my dfs just keeps calling itself till it gets to i = 3 and returns. Silly mistake
That's because you need to remove the elements from the subset before traversing a new path in the decision tree. So, basically all you had to do was add subset.pop() as the final line in your code.
Had the same issue. My problem was that I forgot that since the subset we're editing is technically global, all changes persist even though we pop back up.
@@where3639 Thank you very much! Had just the same question as @OM, now I do understand!
For this particular one, bfs would be cleaner and faster
subset.copy() because this is a deep copy rather than a reference copy correct? great explanation otherwise. i've really over complicated this problem in the past and probably still do. the use of the dfs functon was clever : )
Yup, that's exactly correct!
the answer is still same? so what's the advantage of using copy()?
You don't need backtracking at all. Simple iterative solution would be to iterate from 0 to 2^(size of array nums), check which bits are set in an iteration index and add corresponding element from array nums to current subset. And this is extremely easy to code.
I love you
why is your website not working?
Can you share more details? It's working for me and i haven't heard anyone else having issues.
The C++ solution on your website seems to be a direct copy from the LeetCode website, taking a different approach than the one presented in your video. This complicates the understanding of your video for those using C++. At times, when your explanation is a bit unclear, I find myself merging the code to better comprehend your explanation. However, when the code differs from your video, it becomes challenging to determine which approach I should follow.
where is backtracking happening here?(Assuming Backtracking means not following that path where the solution doesn't exist.) It looks like a recursion where we are taking 2 decision at every step. Can some one explain please?
This is so unintuitive it's wild. Code is often write once read many. So, in a practical sense, no code intended for humans should be written like this ever.
Is it me or understanding recursion and backtracking is a little difficult?
Its difficult but really a saviour. Very tough to grasp for a veginner😢
@@Abubakar91718 thanks! It's been 2 months after posting that comment now I feel I understand it better.
the time complexity is not n * 2^n, it is just 2^n....
In drawing explanation he uses BFS and then in coding it's DFS. I could have been better explanation tbh
Then create your own video