Problem Description
Given an integer array nums, return all possible subsets (the power set).
The solution set must not contain duplicate subsets.
Example 1:
Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10
The description was taken from https://leetcode.com/problems/subsets/.
Problem Solution
#O(N*2^N) Time, O(N*2^N) Spaceclass Solution: def subsets(self, nums: List[int]) -> List[List[int]]: output = [] def backtrack(start:int, combo:list) -> None: if len(combo) == sub_length: output.append(list(combo)) return for i in range(start, len(nums)): combo.append(nums[i]) backtrack(i + 1, combo) combo.pop() for sub_length in range(0, len(nums) + 1): backtrack(0, []) return outputProblem Explanation
If a problem requires us to return all possible combinations of a given input, typically that is an indication that backtracking is a good approach.
Backtracking is a Depth-First Search algorithm where we remove a choice whenever the DFS path yoyo returns to the given function. This allows us to circulate elements into each valid position so that we can generate each valid combination.
A general template for backtracking is to set a base case that appends a valid combination for a given DFS path to the output, if not, check if a placement is valid then make the placement. Once that placement is made, we'd go down a new DFS path with that placement and if that path didn't lead to a solution or it didn't lead to every solution like in this problem, we'd backtrack on the choice to make that placement by removing it from the combination.
Let's start by initializing our output.
output = []
Next, we will create our recursive backtrack function.
The function will take an index to begin a traversal from and a combo list that contains a Depth First Search path's current subset.
def backtrack(start:int, combo:list) -> None:
Before editing a combo any further, we will first check if the length of the combo is equal to the current subset length we are trying to get each combination for.
If it is, we will append the combo to the output and end this recursive path. We will need to take a deep copy of the combo since it will be edited later and we don't want it to be overwritten.
if len(combo) == sub_length: output.append(list(combo)) return
We will now start creating the backtracking logic.
Let's create a loop that will scan the input array from a given starting index to the last index of the array.
This is how we will split up the scope of each subset through recursion.
for i in range(start, len(nums)):
Within a recursive call, we will append the number at the index of the current iterator value, then recurse the function with the current combo and increment the index value by one.
combo.append(nums[i]) backtrack(i + 1, combo)
Once a DFS path is complete, we will backtrack by popping the last value off of our combo so that we can append the next number from our input array and begin a new DFS path until we have each subset for a given length.
combo.pop()
Now that we have our backtrack function built, we will just need to iterate through the different lengths of subsets and get each unique combination for each length.
In other words, we are getting each combination for subsets of length zero, length one, length two, etc.
for sub_length in range(0, len(nums) + 1): backtrack(0, [])
Once we have our output that contains each subset, we will return it.
return output
This illustration shows what the flow of the DFS and backtracking would look like within the third iteration where sub_length = 2.
