package hr.fer.dstankovic.part2;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ValidParenthesis {

    public static void main(String[] args) {
        int num = 7;
        solve(num);
        List<String> l = cache.get(num);
        for (String str : l) {
            System.out.println(str);
        }
    }

    private static List<List<String>> cache = new ArrayList<>();

    static {
        List<String> tmp = new ArrayList<>();
        tmp.add("");
        cache.add(tmp);
    }

    private static void solve(int n) {
        if (cache.size() > n) {
            return;
        }
        solve(n - 1);
        List<String> fin = getFinished(n);
        cache.add(fin);
        return;
    }

    private static List<String> finished;

    private static List<String> getFinished(int n) {
        finished = new LinkedList<>();
        f("", n);
        return finished;
    }

    private static void f(String prevStr, int rem) {
        if (rem <= 0) {
            finished.add(prevStr);
            return;
        }
        for (int i = 1; i <= rem; i++) {
            List<String> l = cache.get(i - 1);
            for (String str : l) {
                f(prevStr + "(" + str + ")", rem - i);
            }
        }
    }

}