Generate All Valid Parentheses - Backtracking / Additional States

https://algo.monster/problems/generate_parentheses

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 :wink:

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