package coding4fun;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Given a list of characters, generate a possible ways to parenthesize the characters.
 *
 * <pre>
 * Input : [a, b]
 * Output: [(a, b)]
 *
 * Input : [a, b, c]
 * Output: [(a(bc)), ((ab)c)]
 *
 * Input : [a, b, c]
 * Output: [(a(b(cd))), (a((bc)d)), ((ab)(cd)),
 *          ((a(bc))d), (((ab)c)d)]
 * </pre>
 */
public class Problem21 {
    private static List<String> generate(List<String> list) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < list.size()-1; i++) {
            List<String> left = generate(list.subList(0, i+1));
            List<String> right = generate(list.subList(i+1, list.size()));
            for (String l : left) {
                for (String r : right) {
                    result.add("(" + l + r + ")");
                }
            }
        }
        if (result.isEmpty()) {
            result.addAll(list);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(generate(Arrays.asList("a", "b")));
        System.out.println(generate(Arrays.asList("a", "b", "c")));
        System.out.println(generate(Arrays.asList("a", "b", "c", "d")));
    }
}

@@ -492,24 +492,91 @@
 ng%3E list) %7B%0A
+        if (list.size() == 1) %7B%0A            return list;%0A        %7D%0A
         List
@@ -975,83 +975,8 @@
   %7D%0A
-        if (result.isEmpty()) %7B%0A            result.addAll(list);%0A        %7D%0A
     

Refactor problem 21