Subsets I II

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

Have you met this question in a real interview? 

Yes

Example

If S = [1,2,3], a solution is:

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

Note

Elements in a subset must be in non-descending order.

The solution set must not contain duplicate subsets.

class Solution {

    /**

     * @param S: A set of numbers.

     * @return: A list of lists. All valid subsets.

     */

    public ArrayList<ArrayList<Integer>> subsets(ArrayList<Integer> S) {

        // write your code here

        ArrayList<ArrayList<Integer>> pre = new ArrayList<ArrayList<Integer>>();

        pre.add(new ArrayList<Integer>());

        Collections.sort(S);

        for(Integer num : S){

            ArrayList<ArrayList<Integer>> next = new ArrayList<ArrayList<Integer>>();

            next.addAll(pre);

            for(ArrayList<Integer> subList : pre){

                ArrayList<Integer> cur = new ArrayList<Integer>(subList);

                cur.add(num);

                next.add(cur);

            }

            pre = next;

        }

        return pre;

    }

}

Given a list of numbers that may has duplicate numbers, return all possible subsets

Have you met this question in a real interview?

Yes

Example

If S = [1,2,2], a solution is:

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

Note

Each element in a subset must be in non-descending order.

The ordering between two subsets is free.

The solution set must not contain duplicate subsets.

class Solution {
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public ArrayList<ArrayList<Integer>> subsetsWithDup(ArrayList<Integer> S) {
        // write your code here
         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
         res.add(new ArrayList<Integer>());
         int start = 0;
         Collections.sort(S);
         for(int i = 0; i < S.size(); i++){
             int curSize = res.size();
             for(int j = start; j < curSize; j++){
                 ArrayList<Integer> newList = new ArrayList<Integer>(res.get(j));
                 newList.add(S.get(i));
                 res.add(newList);
             }
             if((i+1) < S.size() && S.get(i) == S.get(i+1)){
                 start = curSize;
             } else{
                 start = 0;
             }
         }
         
         return res;
    }
}