Sequence one

DFS+剪枝

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int num[1001];
int count_ = 0,len,n,p;
bool flag = false;
struct number
{
  int num;                      //输出的数字
  int pos;                      //数字的下标
}path[1001];

bool check(int c,int e)         //判断前面的数字有无重复
{
  int i;
  for(i = c; i < e; i++)
  {
    if(num[i] == num[e])
    return false;
  }
  return true;
}

  void dfs(int dep,int pos)     //dep：搜索的深度，也就是目前搜索到子串的长度。pos: 当前搜索位置的数字遍历
{
  if(count_ >= p)               //超过输出测试数量
  return;
  if(dep == len)                //搜索到了
  {
    count_++;                   //记录输出的测试数量
    flag = true;
    int i;
    for(i = 0; i < len; i++)
      printf("%d ",path[i].num);
    printf("%d\n",path[i].num); //细节
    return ;
  }
  int i;
  for(i = pos; i < n; i++)
  {
    if(dep == 0 || (dep != 0 && path[dep-1].num <= num[i]))    //判断输出正序
    {
      if(dep == 0 && !check(0,i) )                            //小剪枝：个位数去重
        continue;
      if(dep != 0 && !check(path[dep-1].pos+1,i) )            //小剪枝：检查同前缀的有无重复
        continue;
      path[dep].num = num[i];
      path[dep].pos = i;
      dfs(dep+1,i+1);
    }
  }
  return ;
}
int main()
{
  while(scanf("%d%d",&n,&p) != EOF)
  {
    int i;
    for(i = 0; i < n ; i++)
    {
      scanf("%d",&num[i]);
    }
    count_ = 0;
    for(i = 1; i < n; i++)
    {
      flag = false;
      len = i;                  //输出的子序列长度
      dfs(0,0);
      if(!flag || (count_ >= p))                              //没搜到或者输出超过p
        break;
    }
    printf("\n");
  }
  return 0;
}

笔记：num[]储存输入的数组，path[]储存dfs搜索后的数组排列组合，不满足题意的情况提前用剪枝去除