「[Q&A] 部分和の計算（初心者です）」の動的計画法のコードを書いてみました

　Qiitaの次の質問

の、動的計画法のコードを考えたが、時間がかかりすぎて質問がクローズになっていたので、ここに投稿します。

　dp[j]は和がjとなる数の組（リスト）を要素とするリストとします。
　最初の状態は何も選ばれていなくて和が0であるから、dp[0]は空リストを要素とするリスト[[]]となる。
　$i$番目に和がjになるのは、$i$番目のxs_iを、「選ばず」にか、「選んで」かのどちらか。
　よって遷移式は、$i-1$番目に「和がjになっている数の組を要素とするリスト」と「和がj - xs_iになっている数の組を要素とするリスト」を結合したリストになるので、

dp[j] <- dp[j] + (dp[j - xs_i]の各要素のリストにxs_iを追加したものを要素とするリスト)

となる。
　コードにすると、

def has_subset_sum(xs, k, target):
    max_sum = sum([i for i in xs if i > 0])
    min_sum = sum([i for i in xs if i < 0])

    dp = [[] for _ in range(max_sum - min_sum + 1)]
    dp[0] = [[]]

    for xs_i in sorted(xs):
        for j in range(max_sum, min_sum - 1, -1):
            dp[j] += [[*d, xs_i] for d in dp[j - xs_i] if xs_i not in d and len(d) < k]

    for d in dp[target]:
        if len(d) == k:
            return True

    return False


target = int(input("targetを入力してください:"))
k = int(input("足し合わせる数を入力してください:"))
xs = list(map(int, input().split()))

print(has_subset_sum(xs, k, target))