Poj Solution 1709

http://poj.org/problem?id=1709

#include<iostream>
#include"memory.h"
#include"string.h"
using namespace std;
char word[1000][23];
int index[27];
int n,l,len[1000],set[1000];
void init()
{
    int i;
    for(i=0;i<26;i++)index[i]=n;

    for(i=0;i<n;i++)
    {
        cin>>word[i];
        len[i]=strlen(word[i]);
        if(index[word[i][0]-'a']==n)index[word[i][0]-'a']=i;
    }

    memset(set,1,1000*sizeof(int));
}

char best[100];int go;
char w[100];


void find(int a,int b)
{
    if(go&&strcmp(w,best)>0)return;

    if(b==a&&a)
    {
        if(a==l&&!go)
        {
            strcpy(best,w);go=1;
        }

        else if(a==l&&strcmp(w,best)<0)
            strcpy(best,w);
        return;
    }

    if(a>=l||b>l)return;
    int i,j;
    for(i=(a==0?0:index[w[a]-'a']);i<n&&(a==0||word[i][0]==w[a]);i++)
    if(set[i])
    {
        for(j=a;j<b&&j-a<len[i];j++)
        {
            if(word[i][j-a]!=w[j])break;
        }
        if(j>=b)
        {
            w[a]=0;
            strcat(w,word[i]);
            set[i]=0;                
            if(go&&strcmp(w,best)>0)
            {
                w[b+1]=0;set[i]=1;return;
            }
        
            find(b,a+len[i]);        
            w[b+1]=0;
            set[i]=1;

        }
        if(j-a>=len[i])
        {
            set[i]=0;    
            find(a+len[i],b);
            set[i]=1;
        }
    }
return;

}
int main()
{
    cin>>l>>n;
    init();
    w[0]=0;go=0;
    find(0,0);
    if(n>1&&go)cout<<best<<endl;
    else cout<<"NO SOLUTION"<<endl;
    return 0;
}