Subsets

Published 7 months ago, last updated 7 months ago

Problem

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

This problem is quite straight and can be solved concisely by using Backtracking.

Let's consider the simplest situation: there are no number in given array. We just simply return:

[
 []
]

Now we add a number (whatever it is), let's say: x. The result should be:

[
 [],
 [x]
]

Obviously, we can find the pattern when we add a new number to array: Adding the new number into every list in the previous set and place it in new set. After modifying all list, make a copy of the whole set and paste to new set. For example: now we get a number y besides x. And result should be:

[              [    
 [],     +      [y],      
 [x]            [x,y]  
]              ]

The size of result should be 2 ** n in which n is the size of array.

Below is a sample solution:

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        return helper(nums, 0);
    }
    
    private List<List<Integer>> helper(int[] nums, int index) {
        List<List<Integer>> list;
        if (index == nums.length) {
            List<Integer> l = new ArrayList<>();
            list = new ArrayList<>();
            list.add(l);
            return list;
        }
        list = helper(nums, index + 1);
        List<List<Integer>> newList = new ArrayList<>();
        for (List<Integer> l : list) {
            List<Integer> nl = new ArrayList<>(l);
            nl.add(nums[index]);
            newList.add(nl);
        }
        newList.addAll(list);
        return newList;
    }
}


Comments

    No comment yet



Leave your comment