Subset

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

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

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

Method:

For every element, you have 2 options. You may either include the element in your subset or you will not include the element in your subset.

Solution:

Time: (2^n)
Space: O(n)

public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(ArrayList<Integer> A) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> current = new ArrayList<>();
        Collections.sort(A);
        helper(result, current, A, 0);
        Collections.sort(result, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> A, ArrayList<Integer> B) {
              int size = Math.min(A.size(), B.size());
              for (int i = 0; i < size; i ++) {
                  int a = A.get(i);
                  int b = B.get(i);
                  if (a < b) {
                      return -1;
                  } else if (a > b) {
                      return 1;
                  }
              }
              if (A.size() <= B.size()) {
                  return -1;
              } else {
                  return 1;
              }
            } 
        });
        return result;
    }
    
    private void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> current, ArrayList<Integer> A, int index) {
        if (A.size() == index) {
            Collections.sort(current);
            result.add(new ArrayList<>(current));
            return;
        }
        helper(result, current, A, index + 1);
        current.add(A.get(index));
        helper(result, current, A, index + 1);
        // becasue we are removing the last element, the original list has to be sorted, otherwise we may remove the wrong element
        current.remove(current.size() - 1);
    }
}