This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

A subset of

You are given an array of integers, nums, whose elements are different from each other. Returns all possible subsets (power sets) of this array.

The solution set cannot contain duplicate subsets. You can return the solution set in any order.

Example 1: input output nums = [1, 2, 3], [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Example 2 Input: nums = [0] Output: [[],[0]]

Second, train of thought analysis

  • I’m sure most people think of recursive implementations. Since it’s a subset we have to have a number of our own. Each time the recursion leaves the carrier one length to fill the subset, it can fill out the content.
List<Integer> t = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();

public List<List<Integer>> subsets2(int[] nums) {
    diguiWithLenght(0, nums);
    return ans;
}

public void diguiWithLenght(int cur, int[] nums) {
    if (cur == nums.length) {
        ans.add(new ArrayList<Integer>(t));
        return;
    }
    t.add(nums[cur]);
    diguiWithLenght(cur + 1, nums);
    t.remove(t.size() - 1);
    diguiWithLenght(cur + 1, nums);
}
Copy the code
  • The only thing that needs to happen in recursion is to delete the last data, so that you can go back to the previous path and continue recursion. This is a little bit difficult to understand. Today I take you through another way to open the problem

snowball

  • The author’s implementation is to roll the result set bigger and bigger by snowballing. First we know that an empty array is also a subset. So we add an empty array by default
  • And then the original array[1, 2, 3]I’m going to walk through it and I’m going to add each of the elements individually to the new copy array, which is a little bit abstract to say, but let’s just draw a picture of it

  • When we deal with node 2, we copy the entire result set. Add 2 to the newly replicated node set

  • Repeat until the last element is added. This final result set is all of our subsets. The author close to the production of a set of animation to watch it. Animation animation animation!!

AC code

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> resultList = new ArrayList<>();
    resultList.add(new ArrayList<>());
    for (int num : nums) {
        int length = resultList.size();
        for (int i = 0; i < length; i++) {
            List<Integer> subResult = resultList.get(i);
            List<Integer> temList = newArrayList<>(); temList.addAll(subResult); temList.add(num); resultList.add(temList); }}return resultList;
}
Copy the code

  • After contrast snowball although understanding on convenient point. But it’s a little big in memory. For reference only. Because it’s using an extra array.
  • Why do I need this extra array? Because arrays are passed by reference in Java. If we simply assign the reference object to the past, then we contaminate the original content.

Four,

  • Snowballing is also called expansion. Add content by continuously assigning values to data based on a base data. And then we end up with a set of our subsets

Welcome to the home page