算法题:输出所有正确的括号序列

在简书看到一算法题，如下：

n = 1 输出 ( )
n = 2 输出 ( ) ( ) , ( ( ) )
n = 3 输出 ( ) ( ) ( ), ( ( ) ) ( ), ( ) ( ( ) ), ( ( ( ) ) ), ( ( ) ( ) )
输入任意的n，输出所有正确的()排列？

---

我的思路是用排列的思想做，贴代码：

#include <iostream>
using namespace std;

template <class T> void Swap(T& a, T& b)
{
    T temp = a; a = b; b = temp;
}
typedef char ElemType;

bool is_valid(ElemType *A, int N)
{
    int sum = 0;
    for (int i = 0; i < N; ++i)
    {
        sum += (A[i] == '(' ? 1 : -1);
        if (sum < 0)
        {
            return false;
        }
    }

    return true;
}

//不重复全排列
//交换 递归
//p:表示递归到第p层

void _unrepeat_prem_swap_recursion(ElemType *A, int N, int p)
{
    static int count = 1;
    if (p == N)
    {
        if (!is_valid(A, N))
        {
            return;
        }

        cout << "[" << count << "\t] = ";
        for (int i = 0; i < N; ++i)
        {
           cout << A[i] << " ";
        }
        cout << endl;
        count++;
        return;
    }

    for (int i = p; i < N; ++i)
    {
        //减枝
        //如果A[i]与A[p...i-1]的任一元素相同,则表示这个待生成的序列是重复的,需要跳过
        bool find = false;
        for (int j = p; j < i; ++j)
        {
            if (A[i] == A[j])
            {
                find = true;
                break;
            }
        }
        if (find)
        {
            continue;
        }

        Swap(A[i], A[p]);//交换
        _unrepeat_prem_swap_recursion(A, N, p + 1);
        Swap(A[i], A[p]);//恢复
    }
}

void unrepeat_prem_swap_recursion(ElemType *A, int N)
{
    _unrepeat_prem_swap_recursion(A, N, 0);
}

int main()
{
    int N = 0;
    cout << "enter N:";
    cin >> N;

    ElemType *A = new ElemType[2 * N];
    for (int i = 0; i < N; ++i)
    {
        A[i] = '(';
    }
    for (int i = N; i < 2 * N; ++i)
    {
        A[i] = ')';
    }
    unrepeat_prem_swap_recursion(A, 2 * N);

    return 0;
}

结果如下：

res.png

有其他的思路，欢迎一起讨论！

---

对排列、组合有兴趣的同学可以看下面的链接：

• 排列算法
• 组合算法