Combinations - Leetcode 77 - Python

0:00 - Read the problem
1:30 - Drawing Explanation
5:51 - Coding Explanation

leetcode 77

#combinations #backtracking #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[rentianxiang]

This is second month practicing leetcode problems srsly, you are being so helpful, thank you so much!

[abheykalia]

I was not good at backtracking, but I followed your playlist and coded the soln and then saw ur videos along, and it improved my understanding! Thanks a lot

[harishsn]

Just commenting on this video so that YouTube algorithm picks it up and suggests it more people when they search for a leetcode problem. Because, honestly, this is my favorite channel, along with take__u__forward.

[andrepinto]

range should actually be from start to n-(k-len(comb))+1, so you avoid doing work for combinations that do not have enough numbers left to reach length k.

[tunwailinn]

I was struggling a lot with backtracking problems. Now I can solve it without any help because of your videos. Thanks man!

[jaminchung]

At first I was having so much trouble understanding backtracking. I watched your videos for recursive tree problems and it helped me so much and I started watching your videos for backtracking and I'm beginning to see the pattern template for a majority of these problems. Thank you so much!

[chuanyexiong]

Could anyone explain why need to do comb.pop(), I'm quite comfusing, thanks

[muralidhar]

Great content. I am addicted to this channel. Playing a major role in my preparation. Backtracking, DP, Blind 75 and Graph problems solved are awesome.

Small suggestions :

1)Need some improvement on tree problems. Especially in picking good questions in trees.
2) Please create playlists for strings, queues, heaps similar to graphs and backtracking.

[abhijit-sarkar]

There's an optimization you can do. Instead of looping till n+1, which results in some branches that don't have enough height to make a k-combination, you loop till the last number from which it is possible to make a k-combination.
```
# Number of elements still needed to make a k-combination.
need = k - len(comb)
# The range of numbers is [i, n], therefore, size=n - i + 1
remaining = n - i + 1
# This is the last offset from which we can still make a k-combination.
offset = remaining - need
for i in range(start, start + offset + 1):
```

[sapnavats]

Love your consistent updates! I have a google interview coming up in 2 weeks and i've only recently started doing leetcode. I've done about 120 questions on leetcode. Should I go for leetcode premium or continue with normal questions?

[linshuxi]

Hi, thank you very much for the excellent videos! I am confused on the position of the code "comb.pop()". In the previous videos, the "pop" function appears out of for loop, somtimes it appers in the for loop. In this video, it appers in the "for loop". Can you explain how to decide the position of the "pop" code

[nanke]

This video is awesome! It helps me understand the abstract backtrack algo. Thanks a lot!

[ChristopherJereza]

best breakdown of this problem! thank you

[jinyang]

Splendid explanation! Thank you so much!

[bijayamanandhar]

Hi, thank you for the wonderful explanation of code. I have a question here anyways, why do we need to use the copy() method, why not the straight object? It's also confusing the way pop() method is used to backtrack. let's say (n, k) = (5, 3). In that case how do we get the list [1, 3, 4] as one of the elements of res, for example? Hope our community will be able to help me.

[KTL-rsge]

8:30 Is it necessary to call 'return' with no value? It's hard for me to understand this part

[dhruvchopra]

What if we chose pick or don't pick strategy from Subsets I, and return as soon as size == k, Would the complexity then be reduced down to k*2^n ???
Because we're basically writing the same code and returning a bit earlier.


public void helper(int n, int k, int idx, List<Integer> temp, List<List<Integer>> ans)
{

if(k == temp.size())
{
ans.add(new ArrayList(temp));
return;
}

if(idx > n)
{
return;
}

temp.add(idx);
helper(n, k, idx+1, temp, ans);

temp.remove(temp.size()-1);
helper(n, k, idx+1, temp, ans);
}

[prempeacefulchannel]

Thanks for the amazing explanation, as always

[edwardteach]

U a God. Could you do a vide on:

Longest Substring with At Least K Repeating Characters | Leetcode 395

Question previous marked as hard - but now medium

Read the solution, especially the sliding window approach (since it runs in O(n) times) but I wasn't able to understand it. Other Youtubers who've attempted this problem haven't coded the sliding window approach, most are doing the divide and conquer approach which runs in O(n^2), which I can accept and perform in a technical interview.

[lukengirubiu]

I have a question on the code. What prevents us from going past n+1 for the last value of the list comb for every single iteration.