Backtracking: return all possible subsets given array with possibly duplicate values python
Tue Aug 09 2022 22:02:17 GMT+0000 (Coordinated Universal Time)
Saved by
@bryantirawan
#python
#depth
#first
#search
#recursive
#codesignal
#climb
#list
#solution where you just take subset I and replace last return statement
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
subset = []
result = []
#i is index of subset
def dfs(i):
if i >= len(nums):
result.append(subset.copy())
return
#decision to include nums[i]
subset.append(nums[i])
#this recursive call will be given filled subset
dfs(i + 1)
#decision NOT to include nums[i]
subset.pop()
#this recursive call will be given empty subset
dfs(i + 1)
dfs(0)
#need to remove duplicate sublists within result
return ([list(i) for i in {*[tuple(sorted(i)) for i in result]}])
#solution to prevent duplicates in the first place
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
result = []
nums.sort()
def backtrack(i, subset):
if i == len(nums):
res.append(subset.copy())
return
#all subsets that include nums[i]
subset.append(nums[i])
backtrack(i + 1, subset)
#remove number we just added
subset.pop()
#all subsets that don't include nums[i]
while i + 1 < len(nums) and nums[i] == nums[i + 1]:
i += 1
backtrack(i + 1, subset)
backtrack(0, [])
return result
#solution for array with unique integer array. only last return line is dfferent
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
subset = []
result = []
#i is index of subset
def dfs(i):
if i >= len(nums):
result.append(subset.copy())
return
#decision to include nums[i]
subset.append(nums[i])
#this recursive call will be given filled subset
dfs(i + 1)
#decision NOT to include nums[i]
subset.pop()
#this recursive call will be given empty subset
dfs(i + 1)
dfs(0)
return result
content_copyCOPY
Very similar to subset I neetcode problem. You can just use that and replace last return statement to remove duplicates or prevent duplicate sublists in the first place.
Big O is n2^n
Each spot in sublist has 2 choices to include or not to include. How long is each sublist? n so we get n2^n
So if you had [1, 2, 2, 3] there will be 12 possible outcomes instead of 2^n = 16 because there are 4 duplicates but 2^n is close enough. If you do naive way of calculating all subsets and then removing duplicates it's still n2^n.
Decision tree to prevent duplicates in the first place: https://ibb.co/mbTLtJ1
General concept of preventing duplicates: sort given array. If you skip one number, skip all.
https://leetcode.com/problems/subsets-ii/submissions/
Comments