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