212 lines
4.6 KiB
Markdown
212 lines
4.6 KiB
Markdown
---
|
|
layout: page
|
|
title: Subsets (Backtracking)
|
|
last_solved: 2020-06-22
|
|
category: recursion, backtracking
|
|
leetcode_url: https://leetcode.com/problems/subsets/
|
|
status: Solved
|
|
---
|
|
|
|
Problem
|
|
-------
|
|
|
|
```
|
|
Given a set of distinct integers, nums, return all possible subsets (the power set).
|
|
|
|
Note: The solution set must not contain duplicate subsets.
|
|
|
|
Example:
|
|
|
|
Input: nums = [1,2,3]
|
|
Output:
|
|
[
|
|
[3],
|
|
[1],
|
|
[2],
|
|
[1,2,3],
|
|
[1,3],
|
|
[2,3],
|
|
[1,2],
|
|
[]
|
|
]
|
|
|
|
```
|
|
|
|
Solution
|
|
----------
|
|
|
|
All backtracking problems have this structure, just memorize it.
|
|
|
|
Still not sure why we +1 to index and why that is different from Permutation. This series of articles tries to explain it.
|
|
|
|
[part 1](https://medium.com/algorithms-and-leetcode/backtracking-e001561b9f28)
|
|
[part 2](https://medium.com/algorithms-and-leetcode/backtracking-with-leetcode-problems-part-2-705c9cc70e52)
|
|
[part 3](https://medium.com/algorithms-and-leetcode/in-depth-backtracking-with-leetcode-problems-part-3-b225f19e0d51)
|
|
|
|
|
|
{% highlight python %}
|
|
|
|
def subsets3(nums):
|
|
|
|
def backtrack(currentSubset, allSubsets, nums, index):
|
|
|
|
allSubsets.append( currentSubset.copy() )
|
|
|
|
for i in range(index, len(nums)):
|
|
|
|
currentSubset.append(nums[i])
|
|
print(currentSubset)
|
|
|
|
backtrack( currentSubset, allSubsets, nums, i+1 )
|
|
currentSubset.pop()
|
|
print(currentSubset)
|
|
|
|
|
|
ans = []
|
|
backtrack([], ans, nums, 0)
|
|
return ans
|
|
|
|
{% endhighlight %}
|
|
|
|
|
|
printing the currentSubset at each iteration looks like this:
|
|
```
|
|
[1]
|
|
[1, 2]
|
|
[1, 2, 3]
|
|
[1, 2]
|
|
[1]
|
|
[1, 3]
|
|
[1]
|
|
[]
|
|
[2]
|
|
[2, 3]
|
|
[2]
|
|
[]
|
|
[3]
|
|
[]
|
|
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
______________
|
|
|
|
|
|
Compare these two solutions:
|
|
|
|
{% highlight python %}
|
|
|
|
def subsets5(nums):
|
|
|
|
def helper(start, currentSubset, allSubsets):
|
|
|
|
output.append( currentSubset.copy() )
|
|
|
|
for i in range(start, len(nums) ):
|
|
|
|
currentSubset.append( nums[i] )
|
|
helper(i+1, currentSubset, output)
|
|
currentSubset.pop()
|
|
|
|
output = []
|
|
helper(0, [], output)
|
|
return output
|
|
|
|
|
|
|
|
'''
|
|
recursion without backtracking from timonthy chang
|
|
https://www.youtube.com/watch?v=Mi_C_CMW7vQ
|
|
'''
|
|
def subsets4(nums):
|
|
|
|
output = []
|
|
|
|
def helper(start, currentSubset, output):
|
|
# output += [tmp]
|
|
output.append(currentSubset)
|
|
for i in range(start, len(nums)):
|
|
print( (i+1, currentSubset+[nums[i]]) )
|
|
helper( i+1, currentSubset+[nums[i]], output )
|
|
|
|
helper(0, [], output)
|
|
|
|
return output
|
|
|
|
{% endhighlight %}
|
|
|
|
The output is like this:
|
|
```
|
|
(1, [1])
|
|
(2, [1, 2])
|
|
(3, [1, 2, 3])
|
|
(3, [1, 3])
|
|
(2, [2])
|
|
(3, [2, 3])
|
|
(3, [3])
|
|
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
|
|
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
|
|
```
|
|
|
|
____________
|
|
|
|
|
|
|
|
|
|
______________
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
_______________
|
|
|
|
|
|
Another way is the BFS approach from [educative](https://www.educative.io/courses/grokking-the-coding-interview/gx2OqlvEnWG)
|
|
|
|
|
|
|
|
|
|
```
|
|
|
|
Given set: [1, 5, 3]
|
|
|
|
Start with an empty set: [[]]
|
|
Add the first number (1) to all the existing subsets to create new subsets: [[], [1]];
|
|
Add the second number (5) to all the existing subsets: [[], [1], [5], [1,5]];
|
|
Add the third number (3) to all the existing subsets: [[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]].
|
|
|
|
```
|
|
|
|
|
|
{% highlight python %}
|
|
|
|
def find_subsets(nums):
|
|
subsets = []
|
|
# start by adding the empty subset
|
|
subsets.append([])
|
|
for currentNumber in nums:
|
|
# we will take all existing subsets and insert the current number in them to create new subsets
|
|
n = len(subsets)
|
|
for i in range(n):
|
|
# create a new subset from the existing subset and insert the current element to it
|
|
set = list(subsets[i])
|
|
set.append(currentNumber)
|
|
subsets.append(set)
|
|
|
|
return subsets
|
|
|
|
{% endhighlight %}
|
|
|
|
|
|
Time and space complexity is O(2^n) because we will have 2^n items
|
|
|