Leetcode–Subsets

The Problem:

Given a set of distinct integers, S, 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 S = [1,2,3], a solution is:

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

Notes:

  1. Sort the input list first, and then add each next element to all existing list in result. Remember to add an empty set first.

Java Solution

public class Solution {
    public List<List<Integer>> subsets(int[] S) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        result.add(new ArrayList<Integer>());
        if(S.length==0){
            return result;
        }
        Arrays.sort(S);
        for(int i = 0; i < S.length; i++){
            int len = result.size();
            for(int j = 0; j < len; j++){
                ArrayList<Integer> addlist =  new ArrayList<Integer>(result.get(j));
                addlist.add(S[i]);
                result.add(addlist);
            }
        }
        return result;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s