78. Subsets — LeetCode(Python)
I got you!
Problem:
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
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- All the numbers of
numsare unique.
Solution:
Explanation —
We use a backtracking algorithm to solve this problem.
A subset array is maintained and we consider two cases at each step.
So, we iterate through the array in a recursive manner, creating a decision tree at each iteration.
The first case is when we add the next number in the array to our subset and the second case is when we don’t.
The subset is modified accordingly and the function is called recursively to go further down in the decision tree.
When we hit the end of a path in the tree, i.e. reach a leaf node, we append a copy of the subset to our result array. A copy is needed because, in Python, this array might get modified in the result array as well even if we modify it outside of it.
Finally, we call this backtracking function and return the result array.
Time and Space Complexity —
The creation of the decision tree takes the same amount of time as it takes to generate all subsets, which is of the order of O(n * 2^n).
Also, we require a linear amount of extra space to store our subset variable in the recursion stack as we iterate through all elements in the array.
Thus, if n is the length of the array nums,
Time Complexity: O(n * 2^n)
Space Complexity: O(n)
As we can see, this algorithm is no better than just sorting the coordinates by distance. So, we improve upon this approach in the next part of the solution.
