올바른 괄호의 갯수

from collections import Counter from math import factorial def find_combinations(n, state, combinations): if n < 0: return if n == 0: combinations.append(state[:]) return start = 1 if len(state) == 0 else state[-1] for nextval in range(start, n+1): state.append(nextval) find_combinations(n-nextval, state, combinations) state.pop() def mult(arr): s = 1 for x in arr: s *= x return s def solution(n): a, b = {}, {} a[1], b[1] = 0, 1 for i in range(2, n + 1): # k (2 <= k <= i)개의 수를 합쳐서 i를 만드는 모든 경우의 수를 순회합니다. # 퇴각검색으로 구현합니다. state, combinations = [], [] find_combinations(i, state, combinations) v = 0 for comb in combinations: if len(comb) == 1: continue weight = factorial(len(comb)) / mult(factorial(cnt) for _, cnt in Counter(comb).items()) v += mult(b[x] for x in comb) * weight a[i] = int(v) b[i] = a[i-1] + b[i-1] return a[n] + b[n]