78 Subsets – Medium

Problem:

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

Note:

Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If nums = [1,2,3], a solution is:

[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

Thoughts:

Init solution set with empty list.

Iterating over all numbers, for each number, add it to all existing subsets, but keep the existing subests.

Say for numbers [1, 2, 3],

Init solution set to be []

1: [], [1]

2: [],[1] [2],[1,2]

3: [],[1],[2],[1,2] [3],[1,3],[2,3],[1,2,3]

Solutions:

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null)
            return null;
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        result.add(new ArrayList<Integer>());
        List<List<Integer>> toAddAll = new ArrayList<List<Integer>>();
        for (int i = 0; i < nums.length; i++) {
            toAddAll.clear();
            //get sets that are already in result
            for (List<Integer> a : result) {
                List<Integer> toAdd = new ArrayList<Integer>(a);
                toAdd.add(nums[i]);
                toAddAll.add(toAdd);
            }
            result.addAll(toAddAll);
        }
        //add empty set
        return result;
    }
}

Recursion version:

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        Arrays.sort(nums);
        process(0, nums, result, new LinkedList<Integer>());
        return result;
    }
    private void process(int start, int[] nums, List<List<Integer>> result, List<Integer> curr) {
        result.add(new LinkedList<Integer>(curr));
        for (int i = start; i < nums.length; i ++) {
            curr.add(nums[i]);
            process(i+1, nums, result, curr);
            curr.remove(curr.size() - 1);
        }
    }
}