This is our solution and implementation to problem #78: Subsets on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy our video which outlines our analysis and implementation approach, a breakdown on the space and time complexity, and the full code implementation.
Note: the code and contents here might be slightly different than what is in the video. We've made some improvements to some of the code since recording.
If you would like to view the original problem and solve it, please visit: Subsets on LeetCode.
Problem Analysis
Given a list of integers nums, where each item in the list only appears once, we need to return a list which represents its power set, or a list of lists which cointains:
- An empty list.
- For every item in nums: a list which contains just that element.
- A list of every combination (not permutation) of 2 items.
- A list of every combination of 3, 4, 5, up to n-1 items.
- The original list itself.
Note that the input is a list of integers, but the output is a list of lists of integers. Without delving too much into the math, we know that because we are returning a power set, the number of items in the outer list itself will be 2^n, including the empty list and the original list itself. We can also calculate how many items each sub list will have, but this is not needed for our implementation, so we will omit this analysis. When assembling the set of sets, we will nee to make sure that:
- We have each the empty list and the original input list with the returned list.
- We have lists of each size from 1 up to n-1.
- Each of the combinations are provided in each input size of each list.
Implementation Strategy
We will implement our algorithm by take a recursive approach of splitting up the problem into sub problems. Given a list of size s, we will create the power sets for sublists of size 1, then size 2, ...., up to size s, and along the way, copy over previously generated sublists so we don't need to start from scratch each time. In the diagram below, we take this idea and apply it to an example input of [0, 1, 2]:
- By default, we include the empty list.
- We solve the subproblem of having a list with just 0. We don't repeat the empty list from the previous part, as we already have it.
- We solve the next subproblem, where we have elements [0, 1]. Similarly, we don't repeat list we already have.
- We solve the remaining subproblem, where we have all input elements.
Each section is seperated with a dotted line, so we can see the new entries provided by solving each additional sub-problem. In our algorithm, we will accomplish this implementation by using a loop with iterator i which iterates over the original input items, then a nested loop with iterator j which iterates over the sublists we've formed so far, copies each sublist into a new one, then appends the current item.
Space and Time Complexity
The space complexity, including the output answer, is O(2^n). The set returned by the solution itself will be of size 2^n. The time complexity is O(nā 2^(2n)), as we will be iterating over each element in the input list, then for each, iterating over the partially-generated power set
Additional Resources
- Pascal's Triangle: if needed, we could use this to determine the size of each sub list.
- Discussion and Analysis on YouTube
Full Code
Our solution is given in the Java files below. This solution uses more than one code file. The Main.java file is used as a runner to test locally and includes a few test cases, some from the examples provided by LeetCode and some designed for our own test purposes. The Solution.java file contains the main logic for the solution.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.