I appreciate the rewritten Backtracking section. It’s much more clear! As I’m just getting used to learning the templates for the types of problems, I prefer the solution that uses the for loop. My brain looks for patterns, and I find jumping to the solution with the ifs is actually more jarring and may cause me to not imprint the template in my memory. However, the code snippet that uses the for loop and is shown in the “Footnote” doesn’t account for the step of reverting the additional states. I used the following:
* inside the for loop…
# Update additional states, call dfs(…), then revert the additional states
if parenthsis == ‘(’:
open_count +=1
dfs(path, open_count, close_count, res)
open_count -= 1
else:
close_count += 1
dfs(path, open_count, close_count, res)
close_count -= 1
path.pop()
…
I realize this causes us to repeat the same line in two places, which can be a no-no, but it seems like a better first pass for a novice. The solution with the ifs could be offered up as a refactor.
My apologies, the lines of code didn’t appear in my comment how I typed them. Is there a trick to force a carriage return in these comments?
I think I have a pretty clean solution
def generate_parentheses(n: int) -> List[str]:
# WRITE YOUR BRILLIANT CODE HERE
ret = []
def backtrack(n, openParen, curr):
if n == 0 and openParen == 0:
ret.append(curr)
return
if n > 0:
backtrack(n - 1, openParen + 1, curr + '(')
if openParen > 0:
backtrack(n, openParen - 1, curr + ')')
backtrack(n, 0, '')
return ret
thanks, you are right; we updated the code 
Here’s a neat and efficient way to do this in Python:
from typing import List, Generator
def generate_valid_parens(current_str: str, n: int, open_budget: int, non_closed_parens: int) -> Generator[str, None, None]:
if len(current_str) == 2 * n:
yield current_str
if open_budget > 0:
yield from generate_valid_parens(current_str + '(', n, open_budget - 1, non_closed_parens + 1)
if non_closed_parens > 0:
yield from generate_valid_parens(current_str + ')', n, open_budget, non_closed_parens - 1)
def generate_parentheses(n: int) -> List[str]:
return [result for result in generate_valid_parens('', n, n, 0)]
Looks like ‘start_index’ was not useful here. What type of problems within backtracking would need a start_index?
I’m looking at the C++ version of the solution. I didn’t see any use for the startIndex parameter. Better remove it.
def generate_parentheses(n: int) → List[str]:
def getParenteses(n, validParenteses, path, count):
if count[‘(’] > n or count[‘)’] > count.get(‘(’):
return
if len(path) == n * 2:
validParenteses.append(“”.join(path))
return
for char in ['(', ')']:
path.append(char)
count[char] += 1
getParenteses(n, validParenteses, path, count)
path.pop()
count[char] -= 1
return
if n == 0:
return []
validParenteses = []
count = {'(': 0, ')': 0}
getParenteses(n, validParenteses, [], count)
return validParenteses
THis is my solution as well, the only additional state you need is the number of opening brackets
startIndex is used to track the current level of the state-space tree. it’s not always needed for every problem but we keep it in the template to make it consistent. you will see it used in the next few problems
keep on reading, it’ll show up in the next few articles.
My solution, using pruning rather than states, I guess…
def is_valid(s: str, n:int) -> bool:
"""
for each closing paren, check for preceding open paren
"""
open_count, closed_count = 0, 0
for i in range(len(s)):
if s[i] == '(':
open_count += 1
elif s[i] == ')':
closed_count += 1
if closed_count > open_count:
return False
if open_count > n:
return False
return True
def generate_parentheses(n: int) -> List[str]:
edges = ['(', ')']
index = 0
path = ''
paths = []
def dfs(index, path):
nonlocal paths
if index == n*2:
paths.append(path)
return
for edge in edges:
if not is_valid(path + edge, n):
continue
path += edge
dfs(index + 1, path)
path = path[:-1]
dfs(index, path)
return paths
My solution that almost closely follows the template:
def generate_valid_parentheses(n: int) → List[str]:
output = []
open_param = ‘(’
close_param = ‘)’
paren_to_count_map = {open_param: 0, close_param: 0}
def is_leaf(idx):
return idx >= 2 * n
def is_valid(edge, state):
if edge == open_param:
return state[edge] < n
elif edge == close_param:
return state[edge] < state[open_param]
else:
return False
def get_edges():
edges = (open_param, close_param)
return edges
def dfs(idx, path, state):
if is_leaf(idx):
output.append(''.join(path))
return
for edge in get_edges():
if not is_valid(edge, state):
continue
path.append(edge)
state[edge] += 1
dfs(idx+len(edge), path, state)
path.pop()
state[edge] -= 1
dfs(0, [], paren_to_count_map)
return output
I guess you can’t expect everyone to read through everything lol
It looks to me like startIndex in the Java version isn’t used. I made a simplified version, in which dfs() takes four parameters instead of six.
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.ArrayList;
class Solution {
private static void dfs(String path, int pCount, List<String> result, int n) {
if (path.length() == n * 2) {
if (pCount == 0) result.add(path);
return;
}
if (pCount < n)
dfs(path + '(', pCount + 1, result, n);
if (pCount > 0)
dfs(path + ')', pCount - 1, result, n);
}
public static List<String> generateParentheses(int n) {
List<String> result = new ArrayList<>();
dfs("", 0, result, n);
return result;
}
...
}
This kind of step can often be combined:
path.append('(')
dfs(start_index + 1, path, open_count + 1, close_count, res)
path.pop()
into:
dfs(start_index + 1, path+['('], open_count + 1, close_count, res)
The append and pop steps are taken care of in the function call.
Is
startIndex
even needed in the solution?
My solution. I think just pruning alone will do the trick.
from typing import List
from collections import Counter
def valid(path, n):
counts = Counter(path)
if counts['('] > n or counts[')'] > n or counts[')'] > counts['(']:
return False
return True
def generate_parentheses(n: int) -> List[str]:
res = []
def traverse(state, path):
if state == 2*n:
res.append(''.join(path))
for bracket in ['(', ')']:
path.append(bracket)
if valid(path,n):
traverse(state+1, path)
path.pop()
traverse(0, [])
return res
def generate_parentheses(n: int) -> List[str]:
rst = []
def dfs(cur_path, left_count, right_count):
if left_count == right_count == n:
rst.append(''.join(cur_path))
return
for i, parentness in enumerate(['(', ')']):
if parentness == ')' and left_count <= right_count:
continue
if left_count > n or right_count > n:
continue
cur_path.append(parentness)
if i == 0:
dfs(cur_path, left_count + 1, right_count)
else:
dfs(cur_path, left_count, right_count + 1)
cur_path.pop()
dfs([], 0, 0)
return rst