DEV Community

truongductri01
truongductri01

Posted on

78. Subsets

Problem Source: 78. Subsets

We will start utilizing UMPIRE method

1. Understand the problem
We want to generate a list containing all the subsets of a given list nums.

2. Matching
This problem seems like generating combinations. We can achieve this by utilizing either BFS or DFS algorithm.
And since we establish a larger subset from the smaller ones, we can use Queue to keep track of that.

3. Plan
We want to create an algorithm which can keep adding the elements and create new subset but maintain the order of elements.

For example, if nums = [1,2,3]. The first subset is obviously [].

Starting with [], we can create 3 new subsets: [1], [2], and [3] by adding 1, 2, and 3 into the empty subset to create new ones.

With this, as long as we know which element did the last subset ends with, we can start appending numbers starting from that index to create new subsets.

Here is the algorithm:

  1. Using recursion
  2. At each recursion, we will keep track of (1) the current subset and (2) the index that subset ends with (the index we can start appending element)
  3. Add the current subset into the resulting list. Then repeat the recursion as long as the index is within the limit of the num arrays

4. Implement

class Solution {
    /**
    Utilize recursion / DFS to construct

    Keep track of result List

    each element still need to be able to know what to do next, right?
    */
    private List<List<Integer>> result;
    public void recursion(List<Integer> root, int[] nums, int idx) {
        result.add(root);

        for (int i = idx; i < nums.length; i++) {
            List<Integer> newList = new ArrayList<>(root);
            newList.add(nums[i]);
            recursion(newList, nums, i + 1);
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        result = new ArrayList<>();
        List<Integer> empty = new ArrayList<>();

        recursion(empty, nums, 0);

        return result;
    }
}
Enter fullscreen mode Exit fullscreen mode

5. Review and Evaluate
This algorithm we generate all possible subsets of a list. If a list is of length n, we will have 2^n.

So this problem will not be good to solve in general if the length of the list grows too large

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay