---
# System prepended metadata

title: Untitled

---

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Input: n = 1
Output: ["()"]



n = 2

def backtracking(output, chars_list, open):
    if len(chars_list) == n * 2:
        if open == 0:
            output.append("".join(chars_list))
        return
    if open < n:
        chars_list.append("(")
        open += 1
        backtracking(output, chars_list, open)
        open -= 1
        chars_list.pop(-1)
    if open > 0:
        chars_list.append(")")
        open -= 1
        backtracking(output, chars_list, open)
        open += 1
        chars_list.pop(-1)
        

def main():
    output = []
    backtracking(output, [], 0)
    print(output)


def generateParenthesis(self, n: int) -> List[str]:
        res=[]
        stack=[]
        def backtrack(opened, closed):
            if opened==closed==n:
                res.append("".join(stack))
                return 
            if opened< n:
                stack.append("(")
                backtrack(opened+1, closed)
                stack.pop()
            if closed < opened:
                stack.append(")")
                backtrack(opened, closed+1)
                stack.pop()
        backtrack(0,0)
        return res
        
        
        
        

"""
atlantic_ocean_map = [["0", "1", "1", "0", "0"],
                      ["1", "1", "1", "0", "0"],
                      ["0", "1", "0", "0", "0"],] # 1 island

pacific_ocean_map = [["0", "1", "1", "0", "0"],
                     ["1", "0", "0", "0", "0"],
                     ["0", "1", "1", "0", "0"],] # 3 islands

"""

def NunberIsland(map_a):
    island= 0
    vistited= set()
    rows, cols= len(map_a), len(map_a[0])
    def dfs(r,c):
        if (r < 0 or r >= rows
        or c not in range(cols)
        or map_a[r][c]== "0"
        or (r,c) in visited):
            return 
        visited.add((r,c))
        directions= [(1,0),[-1,0],[0,1],[0,-1]]
        for dr, dc in directions:
            dfs(r+dir[0], c+dir[1])
    for r in range(rows):
        for c in range(cols):
            if map_a[r][c]=="1" and (r,c) not in visited:
                island+=1
                dfs(r,c)
    return island
    

depedencies = {"A": ["B", "C"],
               "B": ["D"],
               "C": ["B"],}
output = ["D", "B", "C", "A"]
output = ["D", "B", "A", "C"]

topological sort

how to detect cycles?
how to find where's the cycle?


str= "bloomberg" 

duplicates = set()
dic={
    "l": 1
}
duplicates.add("b")


O(n)


is it a valid bst tree
