var empty struct{} = struct{}{}

func removeInvalidParentheses(s string) (res []string) {
	l, r := 0, 0
	for _, c := range s {
		if c == '(' {
			l++
		} else if c == ')' {
			if l == 0 {
				r++
			} else {
				l--
			}
		}
	}
	set := make(map[string]struct{})
	dfs(&set, s, []byte{}, 0, l, r, 0)
	for k, _ := range set {
		res = append(res, k)
	}
	return
}

func dfs(set *map[string]struct{}, s string, pre []byte, pos, l, r, cnt int) {
	n := len(s)
	if pos == n && l == 0 && r == 0 && cnt == 0 {
		(*set)[string(pre)] = empty
		return
	} else if cnt < 0 || l < 0 || r < 0 || pos == n {
		return
	}
	if s[pos] == '(' {
		dfs(set, s, pre, pos+1, l-1, r, cnt) // Delete '('
		dfs(set, s, append(pre, '('), pos+1, l, r, cnt+1)
	} else if s[pos] == ')' {
		dfs(set, s, pre, pos+1, l, r-1, cnt) // Delete ')'
		dfs(set, s, append(pre, ')'), pos+1, l, r, cnt-1)
	} else {
		dfs(set, s, append(pre, s[pos]), pos+1, l, r, cnt)
	}
}