Python 競技プログラミング処理高速化二分探索

環境

最近，趣味で競技プログラミングを始めた者です．個人的に使用経験のあるPythonを使っています．
今回のコードの実行環境はatcoderのPython(3.8.2)です．
私がコードの下書きに使っているのは，Google Colabになります．
実行環境でPyPy3(7.3.0)も選べるので利用してみましたが，実行時間はほぼ変わりませんでした．

問題

atcoder内のアルゴリズムと数学演習問題集の，009 - Brute Force 2の問題になります．
もしかしたら，著作権的な問題があるかもしれませんので，お手数をおかけしますが問題は写しません．

リンク先より確認いただければ，幸いです．

質問

Pythonの処理を高速化する方法として，

標準入力においてinput()ではなく，sys.stdin.readlineを使用する
全探索ではなく二分探索を行う
リストlist()ではなく，集合set()を使う

この3点がウェブを調べていてわかりました．1と２の高速化手段を組み合わせたコードと，１と３高速化手段を組み合わせたコードを実装できましたが，満点の条件である実行時間で1000msが切れませんでした．どちらのコードでも1100ms強の実行時間がかかってしまいました．

現状，私ではこれ以上の高速化できないため，他の高速化手段について知りたいと思い，質問しました．

また，Pythonでは，ほぼこれ以上速くならないのであれば，仕方ないので先の問題に進もうと思います．
ちなみに，この問題の元の書籍を購入して読みましたが，基本のコードがC++であるため，参考にはなりませんでした．また，この本の付録的なGithubの参考コードのPythonには，この問題のコードは存在しないようです．

お力添えのほど，よろしくお願いいたします．

1と２の高速化手段を組み合わせたコード

Python
import itertools
import sys
import bisect
input = sys.stdin.readline
a, b = map(int, input().split())
c = input().split()
c = [int(t) for t in c]
s = []
for n in range(a,0,-1):
  for combi in itertools.combinations(c, n):
    s.append(sum(combi))
s.sort()
n = bisect.bisect_left(s, b)
bisect.insort_left(s,b)
if s[n] == s[n+1]:
  print("Yes")
else:
  print("No")

１と３高速化手段を組み合わせたコード

Python
import itertools
import sys
input = sys.stdin.readline
a, b = map(int, input().split())
c = input().split()
c = [int(t) for t in c]
s = set()
for n in range(a,0,-1):
  for combi in itertools.combinations(c, n):
    s.add(sum(combi))
if b in s:
  print("Yes")
else:
  print("No")

ベストアンサーと解決済みコード

本業が忙しく，また動的計画法というものを知らなかったので，解答の理解に時間がかかってしまいました．
kazuma-sさん，lehshellさん，actorbugさん，ご回答いただきありがとうございました．
今回は解決だけでなく，学習につながる解説をしていただいたactorbugさんをベストアンサーとさせていただきます．
actorbugさんが投稿していただいたコードを解釈してみましたので，掲載しておきます．実行時間(63msほど)でした．
私としては，納得できましたが何か間違い等にお気づきの方はコメントいただけると幸いです．

解決済みコードとその解釈

Python
a, b = map(int, input().split()) # aがカードの枚数， bが判定値（判定基準）
c = map(int, input().split()) # cがカードの数値リスト
dp = [True] + [False] * b # dpのノードを作る．最初がtrueなのは， 判定する初期位置の設定？
for n in c: # カードの数値を取り出す．
    for i in range(b - n, -1, -1): # 判定値から，リストの数字を引く．そこから， 値を大きい方から-1ずつ取り出す．indexの0まで
      if dp[i]: # dpのリスト内の値は，真偽値なので帰ってくるのは"True" or "False"だから， Trueの場合は
        dp[i + n] = True # Trueは値としては1だから，dpリスト内の1+（取り出した数値n）をTrueにする．　判定する位置の移動？
print("Yes" if dp[-1] else "No") # リストのindexがTrueならその数値をカードの合計で作れる．最後が判定値なので，"Yes"，Falseなら"No"