首页 > 代码库 > [cc150] Find all valid combinations of n-pairs of parentheses

[cc150] Find all valid combinations of n-pairs of parentheses

2024-07-07 07:27:46   219人阅读

Implement an algorithm to print all valid ( properly opened and closed) combinations of n-pairs of parentheses.

思路：比如 n = 3, ((())) 就是一个valid combination. 这题和前一个 all permutations 有点类似，更 tricky 的地方在于存在大量的重复。

最好的办法是 使用一个 char 缓冲区，长度为2*n. 从左到右往这个缓冲区里填字符 ‘(‘ or ‘)‘，用一个index 指示 当前要填的位置。

那么什么时候填 ( , 什么时候填 ) 呢？规则如下：

假设 缓冲区已经填好一部分了，已经填好的部分里面有 x 个左括号，y 个右括号。

当 x <= n 时，说明左括号还没填完，可以填一个左括号，但是没说此时不能填右括号。

当 y < x <= n 时，此时可以填入右括号的同时保证 properly opened and closed.

其他的情况都是无效的。

public void addParen(int index, int left, int right, char[] buffer, 
            ArrayList<String> result){
        
        int n = buffer.length / 2;
        
        // ensure valid states
        if(left <= n && right <= n && left >= right){
        
            if(left == n && right == n){
                result.add(new String(buffer));
                return;
            }
            
            if(left < n){
                buffer[index] = ‘(‘;
                addParen(index+1, left+1, right, buffer, result);
                //don‘t return, continue instead
            }
            
            if(right < left){
                buffer[index] = ‘)‘;
                addParen(index+1, left, right+1, buffer, result);
            }
        
        }
    }

    public ArrayList<String> generateParens(int n){
        char[] buffer = new char[n * 2];
        ArrayList<String> result = new ArrayList<String>();
        addParen(0, 0, 0, buffer, result);
        return result;
    }

 


联系
我们