# My Java code using DP

• The idea is clear. Use cache to store the already calculated results, from f(0) to f(n). For each f(i), get f(j) and f(i - j - 1) from cache, 0 <= j < = j-1.

``````public static List<String> generateParenthesis(int n) {
List<List<String>> cache = new LinkedList<>();

for (int i = 1; i <= n; i++) {
List<String> nList = new LinkedList<>();
for (int j = 0; j < i; j++) {
List<String> inside = cache.get(j);
List<String> tail = cache.get(i - j - 1);
for (int k = 0; k < inside.size(); k++) {
for (int l = 0; l < tail.size(); l++) {
nList.add("(" + inside.get(k) + ")" + tail.get(l));
}
}
}
}
return cache.get(n);
}``````

• I wonder what is the time complexity for this.

T(0) = 1
T(1) = 1
T(2) = T(0) * T(1)
T(3) = T(0) * T(2) + T(1) * T(1) + T(2) * T(0)
T(n) = 2 * (T(i) * T(n-i-1))

So seems like if T(a) has n items and T(b) has n items, then T(a) * T(b) would take N^2. Now, T(c), let's say, has several of this operations, then T(c) would be N^3. Finally, the whole progression from T(0) to T(n) would take N^4. From the 4 nested loops, I think this is correct?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.