回溯之子集树和排列树

一、子集树
       当所给的问题是从n个元素的集合S中找出满足某种性质的排列时，相应的解空间即使一颗子集树。这类子集树通常有2^n个节叶节点。所需要的时间复杂度是O（2^n）;
      

void Backtrack(int in)
{
    if(in>n)  outpux(x)l;
    else
    for(int i=0;i<=1;i++)
       x[in]=i;
    if(legal(t))
        Backtrack(in+1);
  }

二、排列树
       当所给的问题确定n个元素满足某种性质的排列时，相应的解空间树成为排列树。排列树有n！个叶结点。因此遍历该树所用的时间复杂度是O（n!）
    

void Backtrack(int in)
{
  if(in>n)  outpux(xl;
  else
      for(int i=in;i<=n;i++)
       swap(x[in],x[i]);
       if(legal(t))
          Backtrack(in+1);
       swap(x[in],x[i]);
  }