Published over 1 year ago, last updated over 1 year ago


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:


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<>();
            return list;
        list = helper(nums, index + 1);
        List<List<Integer>> newList = new ArrayList<>();
        for (List<Integer> l : list) {
            List<Integer> nl = new ArrayList<>(l);
        return newList;


    No comment yet

Leave your comment