• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

برنامه‌ای بنویسید که با ورودی گرفتن عدد $n$، همه‌ی زیرمجموعه‌های مجموعه‌ی ${ 1, 2, 3, ..., n }$ را چاپ کند. این زیرمجموعه‌ها را به ترتیب الفبایی مرتب کنید؛ یعنی ابتدا عناصر هر زیرمجموعه را مرتب کنید و سپس به آن‌ها مانند کلمات نگاه کنید و به ترتیبی که در لغت‌نامه می‌آیند مرتب‌شان کنید.

تلاش کنید که این کار را تنها به وسیله‌ی تابع بازگشتی انجام دهید؛ یعنی طوری پیاده‌سازی کنید که این مجموعه‌ها به همین ترتیب تولید و چاپ شوند. (به جای این که ابتدا همه را تولید کرده و سپس مرتب کنید.)

برای آشنایی با قالب خروجی دادن به نمونه‌ها توجه کنید.

ورودی

ورودی تنها شامل یک خط است که در آن یک عدد طبیعی $n$ آمده است. $$1 \le n \le 15$$

خروجی

خروجی برنامه‌ی شما باید شامل $2^n$ خط باشد که در هر خط یک زیرمجموعه چاپ شود.

مثال

ورودی نمونه ۱

1

خروجی نمونه ۱

{}
{1}

ورودی نمونه ۲

3

خروجی نمونه ۲

{}
{1}
{1, 2}
{1, 2, 3}
{1, 3}
{2}
{2, 3}
{3}