无相同元素 提交版.txt

排列问题 M个1,N个0的排列(高效率版) 排列数为:c(m+n,n) 对n个0,m个1,我的想法是这样的: 每个排列可以分三段: 全0列,全1列, 子问题列 设各段长:r,s,t .子问

/*-----------------poj 2245 Lotto-------------------/ 
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
const int S = 52 , nK = 6;
int   k,e[S],ans[S];
bool  used[S];
void Dfs(int depth)
{
   int i;
   if(depth==nK+1)
   { 
	 for(i=1;i<=nK;i++)
	    printf("%d ",ans[i]);
	 printf("\n");
   }
   else 
   { 
	 for(i=1;i<=k;i++)
	 {
		 if(used[i]==0 && e[i]>ans[depth-1]) 
		 {	 
			//关键的剪枝 e[i] > ans[depth-1]使得每个排列内部是升序的,
			//这保证了以后出现的排列不会与先前产生的排列各元素都相同. 
			ans[depth] = e[i];
		    used[i] = 1;
                    Dfs(depth+1);
		    used[i] = 0;
		 }
	 }
   }
}
int main () 
{ 
  int i;
  bool IsFirst = true;
  while(EOF!=scanf("%d",&k))
  {
	 if(k==0)
		break;
     for(i = 1;i<=k;i++)
        scanf("%d", &e[i]);
	 memset(ans,0,sizeof(ans));
	 memset(used,0,sizeof(used));
	 if(IsFirst)
        IsFirst = false;
	 else
        printf("\n");	 	 
	 Dfs(1);	 
  }
  return 0; 
}