[leetcode] 22. Generate Parentheses

DFS

class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val result = mutableListOf<String>()
        
        dfs(n * 2, 0, StringBuilder(), result)
        
        return result
    }
    
    fun dfs(n: Int, cnt: Int, sb: StringBuilder, result: MutableList<String>) {
        if (n == cnt) {
            val parentheses = sb.toString()
            
            if (isWellFormed(parentheses)) result.add(sb.toString())
            
            return
        }
        
        dfs(n, cnt + 1, sb.append("("), result)
        sb.deleteCharAt(sb.lastIndex)
        dfs(n, cnt + 1, sb.append(")"), result)
        sb.deleteCharAt(sb.lastIndex)
    }
    
    fun isWellFormed(parentheses: String): Boolean {
        val stack = Stack<Char>()
        val len = parentheses.length
        
        for (i in 0 until len) {
            when (parentheses[i]) {
                '(' -> stack.push('(')
                ')' -> {
                    if (stack.isEmpty()) return false
                    stack.pop()
                }
            }
        }
        
        return stack.isEmpty()
    }
}

Back Tracking

class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val result = mutableListOf<String>()
        
        dfs(n, "", 0, 0, result)
        
        return result
    }
    
    fun dfs(n: Int, str: String, open: Int, close: Int, result: MutableList<String>) {                
        if (str.length == n * 2) {
            result.add(str)
            return
        }
        
        if (open < n) dfs(n, str + "(", open + 1, close, result)
        if (close < open) dfs(n, str + ")", open, close + 1, result)        
    }
}