この問題の \(S_n\) の定義の内部には \(S_{n-1}\) が登場します。このように、ある対象を記述するときにそれ自身が記述中に登場することを 再帰 と呼びます。
この問題は再帰をうまく扱う方法をテーマとした問題です。いくつかの解法があるので順に説明していきましょう。

1. 再帰関数

再帰関数とは、関数の内部で自分自身を呼び出す関数のことを言います。
\(S_n\) の再帰的な定義は、再帰関数を用いるとそのまま実装することができます。
実装例は以下のようになります。

def S(n):
  if n == 1:
    return [1]
  else:
    return S(n - 1) + [n] + S(n - 1)


N = int(input())
print(*S(N))

上の S(N) は問題文の定義をそのまま記述したような内容になっています。再帰関数を用いるメリットは、このように再帰的な構造をそのままコードを記述できる点にあります。

一方、この問題で再帰を利用する欠点としては、同じ関数・同じ引数の関数呼び出しが何回も発生してしまう点にあります。 この問題では、

• \(S(N)\) の内部で \(S(N-1)\) が \(2\) 回呼び出されて、
• \(S(N-1)\) の内部で \(S(N-2)\) が \(2\) 回呼び出されて、
• \(\vdots\)
• \(S(2)\) の内部で \(S(1)\) が \(2\) 回呼び出されます。

なので \(S(N)\) を呼び出すと \(S(i)\) は \(2^{N-i}\) 回、特に \(S(1)\) は \(2^{N-1}\) 回呼び出される、ということになるわけです。

\(S(N)\) の内部では長さ \(2^N - 1\) の列を生成する計算が行われているので、計算量は全体で

\[\mathrm{O}\left(\sum_{i=1}^N 2^{N-i}(2^{i}-1) \right) = \mathrm{O}(N 2^N - 2^N + 1) = \mathrm{O}(N 2^N)\]

となり、この問題を解く上では問題ありませんが、問題によっては計算量が他の方法よりも爆発的に増加するケースもあるので注意が必要です。(4. の例も参考にしてください)

2. メモ化再帰

再帰関数を覚えた人が次に覚えてほしいのが今から説明する メモ化再帰 です。

再帰の欠点は、上にも書いた通り「同じ引数を何回も無駄に呼び出してしまう」という点にあります。
そこで、関数 \(S(n)\) について、 \(n\) をキー、\(S(n)\) の返り値を値とした辞書(連想配列)を作って、\(S(n)\) を初めて計算するたびに返り値を保存していくことを考えましょう。そして、2 回目以降の呼び出しでは、関数にある処理を行わずに辞書に載っている値を返すようにします。このような処理を挟むことで高速化する手法をメモ化再帰と呼びます。

そうすることで、\(S(n)\) の内部の処理は高々 \(1\) 回しか呼ばれないことになるので、計算量は

\[\mathrm{O}(\sum_{i=1}^N 2^{i}-1) = \mathrm{O}(2^N - 1) = \mathrm{O}(2^N)\]

となり、普通の再帰から少しだけ計算量を改善できます。
実装は次の通りです。

memo = {}

def S(n):
  if n in memo:
    return memo[n]
  if n == 1:
    ret = [1]
  else:
    ret = S(n - 1) + [n] + S(n - 1)
  memo[n] = ret
  return ret


N = int(input())
print(*S(N))

また、Python では lru_cache という機能を使うとメモ化再帰を以下のように少しだけ簡潔に書くことができます。( 3 行目のように @ から始まる行はデコレータと呼ばれるもので、これを書くだけでメモ化再帰が行われます。)

from functools import lru_cache

@lru_cache(maxsize=None)
def S(n):
  if n == 1:
    return [1]
  else:
    return S(n - 1) + [n] + S(n - 1)


N = int(input())
print(*S(N))

3. 動的計画法

この問題は動的計画法、いわゆる DP でも解くことができます。動的計画法とは、小さいサイズの部分問題から順に解いていって答えをメモしていき、大きいサイズの問題は小さいサイズの問題の答えを元に計算するようなアルゴリズムのことを言います。
この問題では \(S(1)\) から順に小さい順に計算していくとうまく動的計画法を適用できます。計算量はメモ化再帰と同じ \(\mathrm{O}(2^N)\) です。実装例は次の通りです。

N = int(input())
dp = [[] for _ in range(N + 1)]
dp[1] = [1]
for n in range(2, N + 1):
  dp[n] = dp[n - 1] + [n] + dp[n - 1]
print(*dp[N])

メモ化再帰と動的計画法は本質的に同じことをやっています。メモ化再帰は結局「小さい問題から \(1\) 回ずつ計算していく」という処理が行われていて、これは動的計画法と結果的に同じような計算手順をたどることになります。

実際、動的計画法は (特殊な高速化を行う問題以外は) メモ化再帰でも解けます。それぞれの長所を挙げると、

• メモ化再帰は再帰構造をそのまま書き下せばよいため、動的計画法より実装しやすいことが多い
• 動的計画法はメモ化再帰と比べて関数呼び出しや辞書を用いたメモ化によるオーバーヘッドが無いぶん実行時間の定数倍が良い

という感じで、問題に応じてメモ化再帰で実装するか DP で実装するかを使い分ける人が多い印象です。

• イメージとしては、基本的には DP を使用するが、桁 DP や区間 DP のような複雑な DP はメモ化再帰で実装する、という人が多い印象があります。

4. おまけ：練習問題

再帰の計算量の話題でよく語られるのがフィボナッチ数列です。

\[f_0 = 0, f_1 = 1, f_{n} = f_{n-1} + f_{n-2} (n \geq 2)\]

def f(n):
  return n if n <= 1 else f(n - 1) + f(n - 2)

print(f(70))

上のコードは \(f_{70}\) を再帰関数を用いて計算するコードですが、計算量が \(\mathrm{O}(1.619^{70})\) と \(10^{16}\) 相当の値になっていてプログラムの実行が到底終わりません。
メモ化再帰や動的計画法を用いて高速に動作するようにしてみましょう。(190392490709135 が出力されたら正解です。)