二次元dpの復元

個人的なメモなので間違ってたらすみません。

問題

N枚のカードが一列に並べられており、左からi番目のカードには整数A_iが書かれています。カードの中からいくつかを選んで書かれた整数の合計がSとなるようにする方法は存在しますか。

input

N S
A_1, A_2,,,A_N

output

選び方が存在すればyes + 使うカードの表示。 存在しなければno。

解法

まずは普通の二次元dpをする
二次元dpをした後にdpの行列から逆戻りして使うカードを拾う

前半のdpで答えが出ている場合のみ処理を行うため合計値と行を最後尾のところからスタートして表の左上に逆戻りしていくことを考える。
tmp_rowをチェックする行番号(=カード番号) ,　tmp_numを選択したカードを差し引いた合計値とする。

もしdp[tmp_row-1][tmp_num]が1だった場合、その行に対応するカードは使用しなくてもよいということになる。また、dp[tmp_row-1][tmp_num-A[tmp_row]]が1だった場合はそのカードを選択したということになる。
選択した場合はtmpに追加していく

#input
N,S = map(int, input().split())
A = list(map(int, input().split()))
A = [0] + A

#dp
dp = [[0 for i in range(S+1)] for _ in range(N+1) ]

for i in range(N+1):
  for j in range(S+1):

    if i == 0:
      dp[0][0] = 1

    if dp[i-1][j] == 1:
      dp[i][j] = 1
    
    if dp[i-1][j-A[i]] == 1 and j-A[i] >= 0:
      dp[i][j] = 1

#結果の出力
if dp[N][S] == 1:
    print('Yes')
else:
    print('No')
    exit()
 
#yesの場合答えから逆戻りして必要なカードを拾う
tmp = []
tmp_num = S
tmp_row = N

while tmp_num > 0:
  print(tmp_num,tmp_row)
  if dp[tmp_row-1][tmp_num] == 1:
    tmp_row -= 1
    #print(f'throw{A[tmp_row+1]}')
  
  elif dp[tmp_row-1][tmp_num - A[tmp_row]] == 1 and tmp_num-A[tmp_row]>= 0:
    tmp.append(A[tmp_row])
    tmp_num -= A[tmp_row]
    tmp_row -= 1
    #print(f'take{A[tmp_row+1]}')

#アンラップしてプリント
print(*tmp)