Real-time Example

e.g. input: "ABC" output: ABC, ABxC, AxBC, AxBxC

Input: String with n letters

Output: List<String>

Solution:

1. n levels, each level consider one schedule

2. each level has two cases, w/ break or w/o

TC: n = string.length() = O(2^n)

SC: O(n)

public class Solution {
   public List<String> schedule(String univ) {
       List<String> res = new ArrayList<>();
       if (univ == null) {
           return res;
       }
       char[] array = univ.toCharArray();
       StringBuilder sb = new StringBuilder();
       helper(array, sb, 0, res);
       return res;
   }

   private void helper(char[] array, StringBuilder sb, int index, List<String> res) {
       if (index == array.length) {
           res.add(sb.toString());
           return;
       }
       sb.append(array[index]);
       //case 1: w/ break
       if (index < array.length - 1) {
           sb.append("x");
           helper(array, sb, index + 1, res);
           sb.deleteCharAt(sb.length() - 1);
       }
       //case 2: w/o break
       helper(array, sb, index + 1, res);
       sb.deleteCharAt(sb.length() - 1);
   }

   public static void main(String[] args) {
       String univ = "ABCD";
       Solution schedule = new Solution();
       System.out.println(schedule.schedule(univ));
   }
}