Subsets - Leetcode 78 - Recursive Backtracking (Python)

Master Data Structures & Algorithms for FREE at AlgoMap.io/
Code solutions in Python, Java, C++ and JS for this can be found at my GitHub repo here: github.com/gah...
Complete DSA Pathway Zero to Hero: • Data Structures & Algo...
Please check my playlists for free DSA problem solutions:
• Fundamental DSA Theory
• Array & String Questions
• 2 Pointers Questions
• Sliding Window Questions
• Binary Search Questions
• Stack Questions
• Linked List Questions
• Tree Questions
• Heap Questions
• Recursive Backtracking...
• Graph Questions
• Dynamic Programming (D...
My Data Science & ML TH-cam Playlist: • Greg's Path to Become ...
Learn Python and Data Science FASTER at mlnow.ai :)
Support the content: / @greghogg
Follow me on Instagram: / greghogg5
Connect with me on LinkedIn: / greghogg
Follow me on TikTok: / greghogg5
Coursera Plus: imp.i384100.ne...
My Favorite Courses:
Data Structures & Algorithms:
- UCalifornia San Diego DSA: imp.i384100.ne...
- Stanford Algorithms: imp.i384100.ne...
- Python Data Structures: imp.i384100.ne...
- Meta Coding Interview Prep: imp.i384100.ne...
Python:
- UMichigan Python for Everybody: imp.i384100.ne...
- Python Mastery from MLNOW.ai: mlnow.ai/cours...
- Google IT Automation w/ Python: imp.i384100.ne...
Web Dev / Full Stack:
- Meta Front-End Developer: imp.i384100.ne...
- IBM Full Stack Developer: imp.i384100.ne...
- Meta Back-End Developer: imp.i384100.ne...
- John Hopkins HTML, CSS & JS: imp.i384100.ne...
- IBM DevOps: imp.i384100.ne...
Cloud Development:
- AWS Fundamentals: imp.i384100.ne...
- GCP Cloud Engineer: imp.i384100.ne...
- Microsoft Azure Fundamentals: imp.i384100.ne...
Game Development:
- Michigan State Unity Development: imp.i384100.ne...
- UColorado C++ for Unreal Engine: www.coursera.o...
SQL & Data Science:
- SQL by MLNOW.ai: mlnow.ai/cours...
- Python for Data Science by MLNOW.ai: mlnow.ai/cours...
- Google Data Analytics: imp.i384100.ne...
- IBM Data Science: imp.i384100.ne...
- IBM Data Engineer: imp.i384100.ne...
Machine Learning & AI:
- ML Mastery at MLNOW.ai: mlnow.ai/cours...
- ML w/ Andrew Ng: www.coursera.o...
- Deep Learning w/ Andrew Ng: imp.i384100.ne...

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@SHIHJUIheh]

Thank you for explaining drawing part in detail, especially the recursive backtracking part ! You made this concept so much easier!!!

[@GregHogg]

You're very welcome 😎

[@chisomedoka5651]

this is gold, so intuitive . Thanks for this

[@anothertechguy-q9g]

Thank you a lot for explaining the transitive parts of backtracking!

[@shubhambajaj4939]

brilliant solution. you just got yourself a new subscriber :)

[@christianjt7018]

thanks Greg your explanations are the best!

[@GregHogg]

Bro I can see from the comments that you're just flying through these questions, good for you honestly!

[@FZRides]

Hi Greg,
I found your video very intuitive. Thanks for sharing such content. Can you please make a video on "Tower of Hanoi" problem using recursion. I am unable to catch the recursive logic behind it. Can you please do it Sir.

[@sampjm1898]

you can use a dp solution :
fn(n)=fn(n-1)+{fn(n-1) and put element_n in every set that return by fn(n-1)},cache the result of f(n).,f(n-1).....
consider you need to solve all the fn(n) you can write a bottom up dp solution,
consider for each fn(n) only need f(n-1) you can just maintain one layer of cache
so basic case is {[element_1],[empty]} for every element in the array add this element to each set and add this set back to the result:
so the 2nd iteration: {[element_1],[empty],
[element_1,element_2],[element_2]} and so on
sorry for my English

[@GregHogg]

I'll have to look into this. Thanks so much for sharing!

[@supremoluminary]

Do you have a link to this? I want to learn it. Thanks.

[@olaf9063]

Great explanation, thanks. Is the time complexity not O(n * 2^n) - reason being that at each of the terminal nodes you need to copy the list, which is an O(n) operation?

[@henryhan8838]

You've inspired me, I was just wondering why we multiplied it by n.

[@DivineEdoka]

I'll like to see how you slve subset ii with this pattern as well

[@nav213]

Would backtracking have to do with recursion? Is it possible to solve this in a non-recursive way? I am asking because it's really difficult to understand the recursive implementation of the code unless you memorize it. Thanks again for you awesome tutorials!!!! cheers

[@GregHogg]

You can memorize the template for how this is done, I promise the best way is through recursion

[@user-hu9nu8xu5g]

bro why don't pick and pick is same backtrack(i+1) and why you recursion left i + 1 i don't understand

[@user-hu9nu8xu5g]

bro how do you move recursion left what is line 12 code back track i + 1 , why you have two backtrack(i+1) can you explain bro

[@just4laughs140]

what does backtrack(i +1) mean

[@m.y.7230]

thanks for explaning dfs in drawing

[@GregHogg]

No problem!

[@hrushikway]

thanks

[@anti-dn541]

Easy to understand for noob like me 👍🏻

[@GregHogg]

Oh that's so great to hear 😊

[@maskedoni3229]

Great solution

[@GregHogg]

Thanks so much!

[@Antinormanisto]

I don't understand(

[@GregHogg]

Maybe try watching it again? Backtracking is REALLY confusing at first