leetcode_gym/_problems/subsets.md

layout, title, last_solved, category, leetcode_url, status

layout	title	last_solved	category	leetcode_url	status
page	Subsets (Backtracking)	2020-06-22	recursion, backtracking	https://leetcode.com/problems/subsets/	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 part 2 part 3

{% 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

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