LeetCode 416: ターゲットの合計を作成する方法

1. ダイナミックプログラミングアプローチ:

まず、与えられた配列の合計を計算し、その合計が奇数であれば、部分集合の合計が等しくなることは不可能です。したがって、偶数である場合のみ解が存在する可能性があります。

次に、与えられた配列を2つの部分集合に分割することを考えます。部分集合の合計が等しくなるためには、配列の要素の組み合わせを選択する必要があります。

以下のステップに従って、配列を走査し、ダイナミックプログラミングを使用して解を見つけることができます。

• 2次元の真偽値のテーブルを作成します。行は0から配列の長さまでの数字を表し、列は0から配列の合計の半分までの数字を表します。テーブルの要素は、その位置までの要素の組み合わせで合計を作成できるかどうかを示します。

• テーブルの初期値を設定します。テーブルの最初の列はTrueに設定し、それ以外の要素はFalseに設定します。

• 配列の要素を1つずつ走査し、テーブルを更新します。各要素について、テーブルの要素がTrueである場合、その位置までの要素の組み合わせに現在の要素を追加することができます。また、テーブルの要素がTrueである場合、その位置までの要素の組み合わせに現在の要素を追加することができます。これを繰り返すことで、テーブルを更新します。

• テーブルの最後の行の中央から始めて、Trueの要素を探します。Trueの要素が見つかった場合、その位置までの要素の組み合わせで合計を作成することができます。

以下は、Pythonでの実装例です:

def canPartition(nums):
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False

    target_sum = total_sum // 2
    dp = [[False] * (target_sum + 1) for _ in range(len(nums) + 1)]
    dp[0][0] = True

    for i in range(1, len(nums) + 1):
        current_num = nums[i - 1]
        for j in range(target_sum + 1):
            if dp[i - 1][j]:
                dp[i][j] = True
            elif j >= current_num and dp[i - 1][j - current_num]:
                dp[i][j] = True

    return dp[len(nums)][target_sum]
# 使用例
nums = [1, 5, 11, 5]
print(canPartition(nums))  # 出力: True

上記のコードでは、与えられた配列 [1, 5, 11, 5] を2つの部分集合に分割し、両方の部分集合の要素の合計が等しくなるかどうかを判断しています。canPartition 関数は、与えられた配列を受け取り、TrueまたはFalseを返します。