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;
    }
}

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