回溯法之子集树与排列树

当所给问题是从n个元素的集合S中找出满足某种性质的子集时，解空间为子集树。

当所给问题是从n个元素的集合S中找出满足某种性质的排列时，解空间为排列树。

回溯法搜索子集树算法描述为：

void backtrack(int  t)

{

if(t>n)   output(x);

else

for(int i=0; i<=1; i++)

{

x[t] = i;

if(constraint(t) && bound(t))      backtrack(t+1);

}

}

回溯法搜索排列树的描述为：

void backtrack(int  t)

{

if(t>n)   output(x);

else

for(int i=t; i

{

swap(x[t], x[i]);

if(constraint(t) && bound(t))      backtrack(t+1);

swap(x[t], x[i]);

}

}