Great solution. This is a better solution than the official Leetcode solution as it honors the spirt of keep/not keep an element that is a hallmark for subset problems.
Love the video as always. For those curious how to calculate the actual number of subsets. Because repeated values are allowed the technical number of subsets is the multiplicity of every element + 1, multiplied together. For instance, for [1, 2, 2], we see 1 appears once and 2 appears twice. So (1 + 1) + (2 + 1) = 2 * 3 = 6. That is the number of subsets. This works because we are determining how many times we can use each value and multiplying those numbers together (e.g. we can use 2, zero, one, or two times, which is 3 choices). I'd imagine 2^n is an appropriate approximation.
I used the same approach you have used for the combinations sum II problem and it worked for this problem too ! def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() res = list() numsLen = len(nums) def back(cur, pos): res.append(cur.copy()) prev = -11 for i in range(pos, numsLen): if prev == nums[i]: continue cur.append(nums[i]) back(cur, i + 1) cur.pop() prev = nums[i] back(list(), 0) return res
Kept the same decision tree as the first subset problem, and I used a hashmap instead to keep track of the duplicates with a frequency.. so at each leaf node the subset should have a frequency of 1. Otherwise we do append it.
played around with what i remembered from the original subsets question: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: subsets, subset = [], [] def dfs(i): if i >= len(nums): subsets.append(subset.copy()) # add subset to res return # base case subset.append(nums[i]) # add curr to subset dfs(i+1) # recurse to go next n = subset.pop() if n in subset: return # avoid a duplicate subset dfs(i+1) dfs(0) return subsets
something i discovered, similar to this solution: if you build a hashmap / histogram of the input, you can then cascade down the frequencies for example, let's say 1: 1 2: 2 Then you can do 1: 1 2: 2 [1,2,2] 1: 1 2:1 [1,2] 1:1 2:0 [1] 1:0 2:2 [2,2] 1:0 2:1 [2] 1:0 2:0 [] Just turn these into subsets by emitting as many of each number as you see in the histogram at the leaves of the decision tree -- and you get all the subsets
at 1:35, [1,2] and [1,2] can not be in the solution, but [2,2] and [1,2,2] can be? Both [2,2] and [1,2,2] have duplicates. Why are they acceptable in the solution? [2,2] and [1,2,2] are not sets? A power set is the set of all subsets. A subset is a set itself. They violate the set principle? Thanks.
[1,2] and [1,2] are identical, [2,2] and [1,2,2] are not, the first one does not include 1 so two of them are different, the response should include unique subset in the list the data type used is list, not set, list can have multiple occurrences, set cannot hope this help
**Note**: Though the above posted code works, it tries to add duplicates to the combinations which set() takes care of eliminating. But the fact that duplicates are being added means that code is taking duplicate branches, which it should not. Actually this question is exactly same as the 'Combination Sum ua-cam.com/video/rSA3t6BDDwg/v-deo.html' with just 1 twist, explained in code comment below: def print_combinations(nums): nums.sort() combos = [] l_nums = len(nums) def backtrack(i, curr_elems): if i == l_nums: combos.append(tuple(curr_elems)) return
prev = None elems = curr_elems[:] for index, num in enumerate(nums[i:], start=i): if num == prev: continue prev = num elems.append(num) backtrack(index+1, elems) elems.pop() """ This extra line here is very important to handle all cases otherwise the for loop will always add something to the curr_elem The case where we don't add anything and just increment index is handled here Plus we are doing it out of loop to avoid duplicates """ backtrack(index+1, elems) backtrack(0, []) return combos
@@VarunMittal-viralmutant Hi Varun, regarding your first solution with the Set, in order to not have to use the set, you have to advance the pointer i beyond the duplicate. Use a while loop that checks if list[i] == list[i+1] then i++ (before your 2nd dfs call) Regarding your second solution, you have an i == l_nums check. If you remove that but keep the append, then you don't need the 2nd backtrack call. The reason why is that in this problem, we want every possible combination, not just the combinations that include the last number.
@@halahmilksheikh Ohk !! I got it now, after drawing the decision tree on whiteboard. You meant this: def backtrack(i, curr_elems): # Append the current set of elements without adding anything combos.append(tuple(curr_elems))
prev = None elems = curr_elems[:] for index, num in enumerate(nums[i:], start=i): if num == prev: continue prev = num elems.append(num) backtrack(index+1, elems) elems.pop() ------------------------- Yes, this works too. It's just the eyes/brain is so used to having a 'return' statement in backtracking solution that without it, it just freaks out :P
I did something a little bit different here, when I drew the graph, I noticed that the duplicate values will always be next to each other in the result, so I did a comparison between the latest element in the solution and the current subset, worked like charm! def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() res = [] sub = [] def dfs(depth): if depth >= len(nums): res.append(sub[:]) return sub.append(nums[depth]) if not res or res[-1] != sub: dfs(depth+1) sub.pop() if not res or res[-1] != sub: dfs(depth+1) dfs(0) return res
could you not just sort the nums array then store every subset in a set to take care of duplicates? since any duplicate would appear the same from the sorted tree (ex. [1,2]. [1,2] instead of [1,2], [2,1] )
I used this approach, but soon realized that it would fail for larger test cases, i.e where the nums contain more than 10 elements.. I know this question has a constraint of length < 10, but in general it would fail. It gives TLE.
at 2:48, the time complexity isn't (2^n)n right? that's the space complexity and time is 2^n? edit: oh nvm because in each dfs, u are doing arr.copy() which leads us to have the n
time limit exceeded. perhaps, the while loop cost too much res = [] nums.sort() def backtrack(i, subSet): res.append(subSet[::]) for j in range(i, len(nums)): if j > i and nums[j] == nums[j - 1]: continue subSet.append(nums[j]) backtrack(j + 1, subSet) subSet.pop() backtrack(0, []) return res This solution could work well
what if there is something like [1,2,3,2,4] sorting it and ignoring multiple 2 will never lead to a valid subset 1,3,2,4. since order is important should we sort ? Found the answer : A subset of a set is any collection of elements that are taken from the original set, regardless of the order.
Why is subset passed in as an argument to the recursive function? Seems like the code works without it, since each recursive stack creates a new subset variable.
based of subset 1 and skipping the same elements on second path class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: sub, subs = [], [] nums.sort() def backtrack(i): if i >= len(nums): return subs.append(sub.copy()) sub.append(nums[i]) backtrack(i+1) sub.pop() while i + 1 < len(nums) and nums[i+1] == nums[i]: i += 1 backtrack(i+1) backtrack(0) return subs
That's where you should consider drawing the decision tree by yourself and you would understand why [2,2] is being added to the result, That's the case while branching out at index 0 you didn't consider 1 and included the other 2 indices i.e. 1 & 2... check out 7:36
I take same appoarch from subsets I with tiny update. My appoarch is to also sort but make a set rather then list where will be stored currently processed values. After sorting values and make this same appoarch we got some duplicate leaf nodes but it's no matter becouse they are not in set at the end. After that processing just loop thought results and convert tuples to list and return result. class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums = sorted(nums) res = set() temp = [] l = len(nums) def dfs(index): if index==l: res.add(tuple(temp.copy())) return
dfs(index+1) temp.append(nums[index]) dfs(index+1) temp.pop() dfs(0) return [list(element) for element in res]
Why backtrack when you can do this class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() result = [[], [nums[0]]] len_result = 1 for i in range(1,len(nums)): len_result_prev = len_result len_result = len(result)
if nums[i-1] != nums[i]: for j in range(len_result): res_copy = result[j].copy() res_copy.append(nums[i]) result.append(res_copy) else: for j in range(len_result_prev,len_result): res_copy = result[j].copy() res_copy.append(nums[i]) result.append(res_copy)
Using set to remove duplicates fun subsetsWithDup(nums: IntArray): List { fun dfs(nums:IntArray, index: Int): List { if (index == 0) { return listOf(listOf(nums.first()), listOf()) } val res = dfs(nums, index - 1) return res + res.map { (it + nums[index]) } } return dfs(nums.sorted().toIntArray(), nums.lastIndex).toSet().toList() }
Looked into this pretty extensively. I don't think there is a difference. Try running both, passes all test cases. So does subset.copy() and runs in the same amount of time and space (run it multiple times). Personally I like .copy() because it makes it more explicit as to what's going on, the whole [:] and [::] syntax is too ambiguous IMO.
2 because for each element, we have 2 options - include it or don't, 2^n because there are n elements in the input array. and we multiply this with n because the length of the longest subset is that array itself(with n elements)....so we always take the largest subset size when it comes to TC. hope this helps!
I used brute force way, it is kinda fast, 73% Runtime and 91% memory class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() dp = set([()]) for n in nums: nextDp = dp.copy() for subset in dp: nextSub = subset + tuple([n]) nextDp.add(nextSub) dp = nextDp return list(dp)
I hate this question. It just makes no sense to me to treat duplicate values as unique when they're in a subset together, but treat them as duplicates when they're not
The total number of recursive function calls will be 2 ^ n - additionally, at each function call a deep copy of the subset generated so far is created and added to the subsets list. This will incur an additional O(n) time (as the maximum number of elements in the currentSubset will be n). So overall, the time complexity of this approach will be O(n⋅2^n).
@@matthewsaucedo2471 > at each function call a deep copy of the subset generated so far is created and added to the subsets list. This only occurs at the leaf nodes, not every recursion.
@@matthewsaucedo2471 hmm yeah but then it would be flat and would be `O(n * 2)` or, if even half the calls spawned a copy, `O(n/2 * 4)`. Continuing on in that series: `O(n/4 * 8)`, `O(n/8 * 16)`, … Seems like it would always reduce down to O(n * 2) or O(n/∞ * nodeCount). --- TBH, I also don't really understand why `leafCount == n!` and not just `2^n`. I need to get better at complexity analysis - seems like people get _real_ hand-wavey about it if it's ever at all complicated.
Considering each subset you generate is of average size n, you'd require O(n) time to append it to your list. I guess this is why we have that extra n.
Also could you do a video on Leetcode #523 - Continuous Subarray Sum? I know its similar to Subarray Sum Equals K, but I find it a little harder to understand.
I came up with this, but still some test cases didn't pass, if u figured it out do let me know, def checkSubarraySum(nums: List[int], k: int) -> bool: if len(nums) < 2: return False if len(nums) == 2 : return True if nums[0]+nums[1] % k == 0 else False for i in range(1,len(nums)): sum = 0 j = i while j >= 0: sum += nums[j] if sum % k == 0: return True j -= 1 return False
Kinda confused: my solution takes 1ms but is completely bruteforce and only beats 37%... using Python3: class Solution(object): def subsetsWithDup(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ nums.sort() def dfs(stuff): storage = [] if not stuff: return [[]] final = stuff.pop() rest = dfs(stuff) for element in rest: new_element = element.copy() new_element.append(final) if element not in storage: storage.append(element) storage.append(new_element) return storage return dfs(nums)
if i >= len(nums): if sorted(lst[:]) not in res: res.append(sorted(lst[:])) rest of the code same as subsets 1 way worse time complexity since u sort every time LOL but just thought it was funny
just put it here: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() subs = [[]] end = 0 for i in range(len(nums)): same_num = i > 0 and nums[i] == nums[i - 1] start = 0 if not same_num else end # skip duplicates end = len(subs) for j in range(start, end): subs.append(subs[j] + [nums[i]]) return subs
"You might be thinking, dynamic programming." - Nope not at all I cant even dynamically program
lol
me core
Thanks for all the videos, I just got an Amazon offer today and these helped me a lot : )
Congrats!! 🎉
Bhai party ?
Hey can you please reveal the position and job location you interviewed for?
@
Aleksander Dukaczewski
@@poojabennabhaktula4883 SDE Intern in Madrid (I applied to all European locations).
@@NeetCode I just don’t
Great solution. This is a better solution than the official Leetcode solution as it honors the spirt of keep/not keep an element that is a hallmark for subset problems.
Yep!!!
Love the video as always. For those curious how to calculate the actual number of subsets. Because repeated values are allowed the technical number of subsets is the multiplicity of every element + 1, multiplied together. For instance, for [1, 2, 2], we see 1 appears once and 2 appears twice. So (1 + 1) + (2 + 1) = 2 * 3 = 6. That is the number of subsets. This works because we are determining how many times we can use each value and multiplying those numbers together (e.g. we can use 2, zero, one, or two times, which is 3 choices). I'd imagine 2^n is an appropriate approximation.
The clarity of thought in your explanations is note worthy :)
Thanks!
I used the same approach you have used for the combinations sum II problem and it worked for this problem too !
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = list()
numsLen = len(nums)
def back(cur, pos):
res.append(cur.copy())
prev = -11
for i in range(pos, numsLen):
if prev == nums[i]:
continue
cur.append(nums[i])
back(cur, i + 1)
cur.pop()
prev = nums[i]
back(list(), 0)
return res
Kept the same decision tree as the first subset problem, and I used a hashmap instead to keep track of the duplicates with a frequency.. so at each leaf node the subset should have a frequency of 1. Otherwise we do append it.
Doing it with a hashmap is 2^n instead of n*2^n right?
@@fadsa342 the n portion is from copying an array to the return list, it's unavoidable
You're still calculating the duplicates then so it doesn't improve runtime. Solution he provides eliminates duplicates as an option entirely
would love to see this your solution
@@esiebomaj
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
subsets = {}
nums.sort()
current = []
def backtrack(i):
if i >= len(nums):
subsets[tuple(current)] = True
return
current.append(nums[i])
backtrack(i+1)
current.pop()
backtrack(i+1)
backtrack(0)
return subsets.keys()
Always excited when I see you post!
Thanks for the video. So basically Subsets I but with a sort and shifting i till it's a different number.
Another workable solution with decision tree
class Solution(object):
def solve(self, nums, n, temp=[]):
if n == 0:
if temp not in self.result:
self.result.append(temp)
return
self.solve(nums, n-1, temp+[nums[n-1]])
self.solve(nums, n-1, temp)
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.result = []
self.solve(sorted(nums), len(nums))
return self.result
I don't understand why the TC is O(N*2^N). Is it because we can have almost N elements equal to each other?
check for 'n' (input) how many calls we are making.
Buddy you are awesome. Love from India❤
played around with what i remembered from the original subsets question:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
subsets, subset = [], []
def dfs(i):
if i >= len(nums):
subsets.append(subset.copy()) # add subset to res
return # base case
subset.append(nums[i]) # add curr to subset
dfs(i+1) # recurse to go next
n = subset.pop()
if n in subset: return # avoid a duplicate subset
dfs(i+1)
dfs(0)
return subsets
something i discovered, similar to this solution:
if you build a hashmap / histogram of the input, you can then cascade down the frequencies
for example, let's say
1: 1
2: 2
Then you can do
1: 1
2: 2
[1,2,2]
1: 1
2:1
[1,2]
1:1
2:0
[1]
1:0
2:2
[2,2]
1:0
2:1
[2]
1:0
2:0
[]
Just turn these into subsets by emitting as many of each number as you see in the histogram at the leaves of the decision tree -- and you get all the subsets
Hey, got a code snippet for this? Can't figure out how to go about it.
@@markolainovic yes, i’ll open up leetcode and find my solution for you later today :)
@@vadimkokielov2173 Thanks! ^.^
@@vadimkokielov2173 wheres the code, you liar.
at 1:35, [1,2] and [1,2] can not be in the solution, but [2,2] and [1,2,2] can be? Both [2,2] and [1,2,2] have duplicates. Why are they acceptable in the solution? [2,2] and [1,2,2] are not sets? A power set is the set of all subsets. A subset is a set itself. They violate the set principle? Thanks.
[1,2] and [1,2] are identical, [2,2] and [1,2,2] are not, the first one does not include 1 so two of them are different, the response should include unique subset in the list
the data type used is list, not set, list can have multiple occurrences, set cannot
hope this help
This guy is a gem
This solution works just fine, nothing fancy required with adjusting 'i' :
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
combinations = set()
nums.sort()
def dfs(i, curr_elem):
if i >= len(nums):
combinations.add(tuple(curr_elem))
return
elems = curr_elem[:]
elems.append(nums[i])
dfs(i+1, elems)
elems.pop()
dfs(i+1, elems)
dfs(0, [])
return combinations
**Note**: Though the above posted code works, it tries to add duplicates to the combinations which set() takes care of eliminating. But the fact that duplicates are being added means that code is taking duplicate branches, which it should not.
Actually this question is exactly same as the 'Combination Sum ua-cam.com/video/rSA3t6BDDwg/v-deo.html' with just 1 twist, explained in code comment below:
def print_combinations(nums):
nums.sort()
combos = []
l_nums = len(nums)
def backtrack(i, curr_elems):
if i == l_nums:
combos.append(tuple(curr_elems))
return
prev = None
elems = curr_elems[:]
for index, num in enumerate(nums[i:], start=i):
if num == prev:
continue
prev = num
elems.append(num)
backtrack(index+1, elems)
elems.pop()
"""
This extra line here is very important to handle all cases
otherwise the for loop will always add something to the curr_elem
The case where we don't add anything and just increment index is handled here
Plus we are doing it out of loop to avoid duplicates
"""
backtrack(index+1, elems)
backtrack(0, [])
return combos
@@VarunMittal-viralmutant Hi Varun, regarding your first solution with the Set, in order to not have to use the set, you have to advance the pointer i beyond the duplicate. Use a while loop that checks if list[i] == list[i+1] then i++ (before your 2nd dfs call)
Regarding your second solution, you have an i == l_nums check. If you remove that but keep the append, then you don't need the 2nd backtrack call. The reason why is that in this problem, we want every possible combination, not just the combinations that include the last number.
@@halahmilksheikh I understand the while loop check for the first solution. But didn't understand the i==l_num check in the second
@@halahmilksheikh Ohk !! I got it now, after drawing the decision tree on whiteboard. You meant this:
def backtrack(i, curr_elems):
# Append the current set of elements without adding anything
combos.append(tuple(curr_elems))
prev = None
elems = curr_elems[:]
for index, num in enumerate(nums[i:], start=i):
if num == prev:
continue
prev = num
elems.append(num)
backtrack(index+1, elems)
elems.pop()
-------------------------
Yes, this works too. It's just the eyes/brain is so used to having a 'return' statement in backtracking solution that without it, it just freaks out :P
Thanks for the drawing followed by code flow, very well explained
I did something a little bit different here, when I drew the graph, I noticed that the duplicate values will always be next to each other in the result, so I did a comparison between the latest element in the solution and the current subset, worked like charm!
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
sub = []
def dfs(depth):
if depth >= len(nums):
res.append(sub[:])
return
sub.append(nums[depth])
if not res or res[-1] != sub:
dfs(depth+1)
sub.pop()
if not res or res[-1] != sub:
dfs(depth+1)
dfs(0)
return res
i did same too!
It's the best explanation!
I believe the children under the first [2] should be blue. Love the vid, just posting in case someone else has the same question/concern/thought.
could you not just sort the nums array then store every subset in a set to take care of duplicates? since any duplicate would appear the same from the sorted tree (ex. [1,2]. [1,2] instead of [1,2], [2,1] )
I used this approach, but soon realized that it would fail for larger test cases, i.e where the nums contain more than 10 elements.. I know this question has a constraint of length < 10, but in general it would fail. It gives TLE.
@@AbhishekSharma-vb9ux true for bigger lengths it would take longer, but we are given constraints.
Favorite LC channel
at 2:48, the time complexity isn't (2^n)n right? that's the space complexity and time is 2^n?
edit: oh nvm because in each dfs, u are doing arr.copy() which leads us to have the n
thanks for the video. I was struggling to understand this.
time limit exceeded.
perhaps, the while loop cost too much
res = []
nums.sort()
def backtrack(i, subSet):
res.append(subSet[::])
for j in range(i, len(nums)):
if j > i and nums[j] == nums[j - 1]:
continue
subSet.append(nums[j])
backtrack(j + 1, subSet)
subSet.pop()
backtrack(0, [])
return res
This solution could work well
what if there is something like [1,2,3,2,4] sorting it and ignoring multiple 2 will never lead to a valid subset 1,3,2,4. since order is important should we sort ?
Found the answer : A subset of a set is any collection of elements that are taken from the original set, regardless of the order.
Thanks for all the videos,
thanks for such a great explanation brother
wondering why I'm getting a "list out of range error" when I rearrange the while conditions 🤔
I think we get "index out of bound" error when we change the order because i+1 gets out of bound and we still try to access the number in nums[i+1].
@@niloofaryousefi1757 yes . Thanks for that
great logic man!
Why is subset passed in as an argument to the recursive function? Seems like the code works without it, since each recursive stack creates a new subset variable.
Excellent explanation
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
length = len(nums)
res = []
subsets = []
def dfs(i):
if i >= length:
subsets.append(res.copy())
return 1
res.append(nums[i])
dfs(i+1)
res.pop()
while i+1 < length and nums[i] == nums[i+1]:
i += 1
dfs(i+1)
dfs(0)
return subsets
I think if you are new to leetcode maybe just use a set to do memorization, you might have a easier time
based of subset 1 and skipping the same elements on second path
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
sub, subs = [], []
nums.sort()
def backtrack(i):
if i >= len(nums):
return subs.append(sub.copy())
sub.append(nums[i])
backtrack(i+1)
sub.pop()
while i + 1 < len(nums) and nums[i+1] == nums[i]:
i += 1
backtrack(i+1)
backtrack(0)
return subs
Thanks for the explaination
Hi neetcode, we could've filtered the input and remove duplicates and then find subsets also?
No. If the list is (1,2,2), removing 2 will not give the subsets (2,2) and (1,2,2).
why does it happent that we include [2,2] ? Why did this loop not skip the second '2' when it was the same as previous element?
That's where you should consider drawing the decision tree by yourself and you would understand why [2,2] is being added to the result, That's the case while branching out at index 0 you didn't consider 1 and included the other 2 indices i.e. 1 & 2... check out 7:36
I take same appoarch from subsets I with tiny update.
My appoarch is to also sort but make a set rather then list where will be stored currently processed values.
After sorting values and make this same appoarch we got some duplicate leaf nodes but it's no matter becouse they are not in set at the end.
After that processing just loop thought results and convert tuples to list and return result.
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
res = set()
temp = []
l = len(nums)
def dfs(index):
if index==l:
res.add(tuple(temp.copy()))
return
dfs(index+1)
temp.append(nums[index])
dfs(index+1)
temp.pop()
dfs(0)
return [list(element) for element in res]
Great explanation, as always :) just wondering why I get "index out of range" error, when I rearrange the conditions of the while loop 🤔
I think we get "index out of bound" error when we change the order because i+1 gets out of bound and we still try to access the number in nums[i+1].
"i+1
sooooooooooooo good, subset2 make how backtrack works in subset1 more clear
Thank You!
In one world, there is a 2. In another world, the 2 don't exist!
this is pretty similar to unbounded knapsack :)
why complexity is o(n*2^n) ? not o(2^n)?
Also would like to know.
why we have to sort our input list
Why backtrack when you can do this
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = [[], [nums[0]]]
len_result = 1
for i in range(1,len(nums)):
len_result_prev = len_result
len_result = len(result)
if nums[i-1] != nums[i]:
for j in range(len_result):
res_copy = result[j].copy()
res_copy.append(nums[i])
result.append(res_copy)
else:
for j in range(len_result_prev,len_result):
res_copy = result[j].copy()
res_copy.append(nums[i])
result.append(res_copy)
return result
nice
Using set to remove duplicates
fun subsetsWithDup(nums: IntArray): List {
fun dfs(nums:IntArray, index: Int): List {
if (index == 0) {
return listOf(listOf(nums.first()), listOf())
}
val res = dfs(nums, index - 1)
return res + res.map { (it + nums[index]) }
}
return dfs(nums.sorted().toIntArray(), nums.lastIndex).toSet().toList()
}
Why does it need to be sorted?
Why are you doing " res.append(subset[ :: ]) " and not just " res.append(subset[ :: ]) " . What is the difference between them
Looked into this pretty extensively. I don't think there is a difference. Try running both, passes all test cases. So does subset.copy() and runs in the same amount of time and space (run it multiple times). Personally I like .copy() because it makes it more explicit as to what's going on, the whole [:] and [::] syntax is too ambiguous IMO.
Can somebody explain me why the TC is O(N*2^N)?
2 because for each element, we have 2 options - include it or don't, 2^n because there are n elements in the input array. and we multiply this with n because the length of the longest subset is that array itself(with n elements)....so we always take the largest subset size when it comes to TC. hope this helps!
Thanks a lot. helps so much!!
On line 8, why use `res.append(subset[::])` and not `res.append(subset[:])`?
No reason, just his preferences
I used brute force way, it is kinda fast, 73% Runtime and 91% memory
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
dp = set([()])
for n in nums:
nextDp = dp.copy()
for subset in dp:
nextSub = subset + tuple([n])
nextDp.add(nextSub)
dp = nextDp
return list(dp)
great, you don't need to pass 'subset' as an argument.
It wasn't clear why the input array needs to be sorted. Could you make that more clear? :)
sorting can make the execution of the while loop part easier. it is easier to increment the indices of dulicate elements when the array is sorted
good video
I hate this question. It just makes no sense to me to treat duplicate values as unique when they're in a subset together, but treat them as duplicates when they're not
Ooooooooooooh now I got it!
Why is the time complexity the number of combinations times the length of the longest combination? I.e. why `n * n!` instead of `n!`?
The total number of recursive function calls will be 2 ^ n - additionally, at each function call a deep copy of the subset generated so far is created and added to the subsets list. This will incur an additional O(n) time (as the maximum number of elements in the currentSubset will be n). So overall, the time complexity of this approach will be O(n⋅2^n).
@@matthewsaucedo2471
> at each function call a deep copy of the subset generated so far is created and added to the subsets list.
This only occurs at the leaf nodes, not every recursion.
@@PippyPappyPatterson
Hm - this is a good point. I suppose in the worst case, each of your recursive calls resulting in a call that spawns a copy?
@@matthewsaucedo2471 hmm yeah but then it would be flat and would be `O(n * 2)` or, if even half the calls spawned a copy, `O(n/2 * 4)`.
Continuing on in that series:
`O(n/4 * 8)`, `O(n/8 * 16)`, …
Seems like it would always reduce down to O(n * 2) or O(n/∞ * nodeCount).
---
TBH, I also don't really understand why `leafCount == n!` and not just `2^n`. I need to get better at complexity analysis - seems like people get _real_ hand-wavey about it if it's ever at all complicated.
I do not get why is it n*2^n shouldn't it be just 2^n
Considering each subset you generate is of average size n, you'd require O(n) time to append it to your list. I guess this is why we have that extra n.
@@abhishekc3556 Decent rational. Danke shaye, shambala, inshalla, and mariskahargitay.
@@PippyPappyPatterson whaaat??
@@abhishekc3556 I share my culture with you.
@@PippyPappyPatterson cool
Also could you do a video on Leetcode #523 - Continuous Subarray Sum? I know its similar to Subarray Sum Equals K, but I find it a little harder to understand.
I came up with this, but still some test cases didn't pass, if u figured it out do let me know,
def checkSubarraySum(nums: List[int], k: int) -> bool:
if len(nums) < 2: return False
if len(nums) == 2 : return True if nums[0]+nums[1] % k == 0 else False
for i in range(1,len(nums)):
sum = 0
j = i
while j >= 0:
sum += nums[j]
if sum % k == 0:
return True
j -= 1
return False
Kinda confused: my solution takes 1ms but is completely bruteforce and only beats 37%... using Python3:
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
def dfs(stuff):
storage = []
if not stuff:
return [[]]
final = stuff.pop()
rest = dfs(stuff)
for element in rest:
new_element = element.copy()
new_element.append(final)
if element not in storage:
storage.append(element)
storage.append(new_element)
return storage
return dfs(nums)
Thanks a lot..
This is a similar pattern to combination sum
if i >= len(nums):
if sorted(lst[:]) not in res:
res.append(sorted(lst[:]))
rest of the code same as subsets 1
way worse time complexity since u sort every time LOL but just thought it was funny
backtrack is so hard ==
soooooooooooooooooo good
♥
Lol.too hard to understand
hang in there
just put it here:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
subs = [[]]
end = 0
for i in range(len(nums)):
same_num = i > 0 and nums[i] == nums[i - 1]
start = 0 if not same_num else end # skip duplicates
end = len(subs)
for j in range(start, end):
subs.append(subs[j] + [nums[i]])
return subs