Friday, May 1, 2015

[LeetCode] Subsets

Subsets

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],
  []
]

Solution: The beauty of recursion!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        ArrayList<List<Integer>> list = new ArrayList<List<Integer>>();
        if (nums.length == 0) {
            ArrayList<Integer> l = new ArrayList<Integer>();
            list.add(l);
            return list;
        }
        Arrays.sort(nums);
        List<List<Integer>> li = subsets(
                Arrays.copyOfRange(nums, 0, nums.length - 1)
            );
        list.addAll(li);
        for (List<Integer> ll : li) {
            ArrayList<Integer> l = new ArrayList<Integer>(ll);
            l.add(nums[nums.length - 1]);
            list.add(l);
        }
        return list;
    }
}

No comments:

Post a Comment