# Use DP to solve the problem but, OJ say the answer is wrong

• Here is the idea of the code, for
If we know the list of string in N-1
Then we can get N with
'()' + x or '(' + x + ')' or x + '()' except there is a case if x like '()()', we just need to avoid this duplication
Here is my code

``````class Solution:
# @param {integer} n
# @return {string[]}
def generateParenthesis(self, n):
if n <= 0:
return []
result = {}
result[1] = ['()']
if n == 1:
return result[1]
for i in xrange(2, n+1):
temp = []
for curr in result[i-1]:
temp.append('('+curr+')')
temp.append('()'+curr)
if curr != '()'* (i-1):
temp.append(curr+ '()')
result[i] = temp
return result[n]
``````

For test case 4, my answer are the same as OB, but order is different.

Here is my result for n=4

``['(((())))', '()((()))', '((()))()', '(()(()))', '()()(())', '()(())()', '((())())', '()(())()', '(())()()', '((()()))', '()(()())', '(()())()', '(()()())', '()()()()']``

• I followed the same approach as you and a quick check on the n=4 testcase made me realize that the expected result contained following structure (())(()), which basically cannot be produced (or at least not without further enhancement) by the DP approach. Therfore I just went with the backtracking approach.

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