# Backtracking: return all possible subsets given array with possibly duplicate values python

Tue Aug 09 2022 22:02:17 GMT+0000 (UTC)

```#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/