1.1. All Subsets I

Print all subsets of a set

Assumption: No duplicate

Input: String set {"abc"} with size n

Output: List<String> res

Corner cases: set == null, return res first

Data structure: StringBuilder

Solution:

1. n levels in the tree. For each level, consider adding each letter or not.

2. 2 states/branches: add or not

3. Stop condition: when all letters have been considered

TC: n=# of nodes in the tree: 1+2+4+8+...2^n * Picking from the string n times= O(2^n)

SC: n=height of the tree: # of letters in the string

n on heap(StringBuilder) + n on call stack = O(n)

public List<String> subSets(String set) {
   List<String> res = new ArrayList<>();
   //corner case
   if (set == null) {
     return res;
   }
   char[] array = set.toCharArray(); 
   StringBuilder sb = new StringBuilder();
   helper(array, sb, 0, res);
   return res;
 }

 private void helper(char[] array, StringBuilder sb, int index, List<String> res) {
   //base case: when all letters are used
   if (index == set.length) {   
     res.add(sb.toString());
     return;  
   }
   helper(array, sb, index + 1, res);	//state 1: not adding
   helper(array, sb.append(array[index]), index + 1, res);    //state 2: adding at position index
   sb.deleteCharAt(sb.length() - 1); 	//remove added char before returning to previous level
 }