#include <iostream>
#include <list>

using namespace std;

typedef list<int> integer;

bool is_valid(int y){
  return 0<=y && y<=9;
}

list<integer> cons(int x, list<integer> xs){
	for(list<integer>::iterator it=xs.begin(); it!=xs.end(); ++it)
		(*it).push_front(x);
	return xs;
}

integer cons(int x1, int x2){
	integer x;
	x.push_front(x2);
	x.push_front(x1);
	return x;
}

list<integer> append(list<integer> xs, list<integer> ys){
	for(list<integer>::iterator it=ys.begin(); it!=ys.end(); ++it)
		xs.push_front(*it);
	return xs;
}

list<integer> next_digit(integer ds, int y){
	list<integer> res;
	int d=ds.front();
	integer xs=cons(y+d, y-d);
	for(integer::iterator it=xs.begin(); it!=xs.end(); ++it){
	  int x=*it;
	  if(is_valid(x)){
		ds.pop_front();
		if(ds.empty())
			res.push_back(cons(y,x));
		else
			res=append(res, cons(y, next_digit(ds, x)));
		ds.push_front(d);
	  }
	}
	return res;
}

list<integer> expand_digit(integer ds){
	list<integer> res;
	for(int x=1; x<=9; ++x)
		res=append(res, next_digit(ds, x));
	return res;
}

void print_integer(integer x){
	for(integer::iterator it=x.begin(); it!=x.end(); ++it)
		cout<<*it;
}

void print_integers(list<integer> xs){
	for(list<integer>::iterator it=xs.begin(); it!=xs.end(); ++it){
		print_integer(*it);
		cout<<", ";
	}
}

void search(list<integer> xs, int digit){
	list<integer> res;
	for(list<integer>::iterator it=xs.begin(); it!=xs.end(); ++it){
		res=append(res, expand_digit(*it));
		print_integers(res);
	}
	if(digit-1)
		search(res, digit-1);
}

int main(int, char**){
	integer x0;
	x0.push_back(7);
	list<integer> res;
	res.push_back(x0);
	cout<<"max digit of the lucy number:";
	int i;
	cin>>i;
	search(res, i-1);
}

lucky [] x0 = [[]]
lucky (d:ds) x0 = [x1:xs | x1<-[x0+d, x0-d], xs<-(lucky ds x1), (x1>=0 && x1<=9)]

lucky_numbers ds = [ x1:xs | x1<-[1..9], xs<-lucky ds x1]