在简书看到一算法题，如下：
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
有其他的思路，欢迎一起讨论！
对排列、组合有兴趣的同学可以看下面的链接：
