題目資訊

題目編號: 416
題目連結: Partition Equal Subset Sum
主題: Array, Dynamic Programming

題目敘述

給定一個整數數組 nums，返回 true 如果你能將該數組分割成兩個子集，使得兩個子集的元素總和相等，否則返回 false。

範例 1:

輸入: nums = [1,5,11,5]
輸出: true
解釋: 該數組可以分割成 [1, 5, 5] 和 [11]。

範例 2:

輸入: nums = [1,2,3,5]
輸出: false
解釋: 該數組無法分割成總和相等的子集。

限制條件:

$1 \leq \text{nums.length} \leq 200$
$1 \leq \text{nums}[i] \leq 100$

直覺

這個問題是計算機科學中著名的"分割問題"的經典例子，主要目標是判斷是否能將給定的整數列表分成兩個子集，其中每個子集中的元素和相等。此問題的挑戰在於需要確保這些子集的和相等，而不僅僅是任何數字的劃分。

關鍵的觀察點是，如果數組的總和為奇數，則不可能將其劃分成兩個相等的整數子集。因此，任何可行的解決方案都要求總和為偶數，這樣我們就可以將每個子集的目標和設為總和的一半。

解法

為了解決這個問題，我們使用了一種具有記憶化功能的動態規劃方法，其通過存儲子問題的中間結果來優化遞歸過程。

初始設定：
- 計算數組的總和。如果它是奇數，則立即返回 false，因為不可能將一個奇數和劃分成兩個相等的子集。
- 將 target 設為總和的一半。現在的目標是確定是否存在一個子集，使其和等於 target。
動態規劃表格：
- 初始化一個二維向量 dp，使得 dp[i][j] 將存儲一個可選的布林值，指示是否能使用 nums 的前 i 個元素來達成子集和 j。
帶有記憶化的遞歸檢查：
- 使用第一個元素（idx = 0）和計算出的 target 開始遞歸過程。
- 基礎情況：
  - 如果當前索引超過 nums 的長度，返回 false，因為沒有額外的元素可供考慮。
  - 如果達到 target（target == 0），返回 true，因為已找到等價的分割子集。
  - 如果 dp[idx][target] 的結果已經計算過，返回其值以避免冗餘計算。
遞歸探索：
- 包含當前元素：檢查如果將當前元素包含在子集中（即 target - nums[idx]），是否仍能通過遞歸檢查 canPartition(nums, idx + 1, target - nums[idx]) 達到 target。
- 排除當前元素：如果包含當前元素不導致成功，嘗試排除它，通過檢查 canPartition(nums, idx + 1, target)。
記憶化：
- 將每次遞歸調用的結果存儲在 dp[idx][target] 中，以防止重複工作並確保效率。

這些步驟的組合確保每種可能性都被有效地探索，同時存儲和重用先前計算的結果，從而將計算複雜度從指數縮減到多項式時間。

程式碼

C++

class Solution {
public:
    // 聲明一個二維向量用於記憶化儲存中間結果
    vector<vector<optional<bool>>> dp;

    bool canPartition(vector<int>& nums, int idx = -1, int target = -1) {
        // 初始呼叫設定
        if (idx == -1) {
            // 計算數組元素的總和
            target = accumulate(nums.begin(), nums.end(), 0);

            // 如果總和為奇數，則不可能分割成相等的子集
            if (target & 1) return false;

            // 每個子集所需的目標和是總和的一半
            target /= 2;

            // 清除並調整dp向量的大小以配合當前nums大小和目標和
            dp.clear();
            dp.resize(nums.size(), vector<optional<bool>>(target + 1, nullopt));

            // 開始從索引0進行遞歸搜尋
            return canPartition(nums, 0, target);
        } else {
            // 基本情況：考慮了所有元素，如果未達到目標返回false
            if (idx >= nums.size()) return false;

            // 如果這個子問題已經解決，返回儲存的結果
            if (dp[idx][target].has_value()) return dp[idx][target].value();

            // 如果目標和為零，則成功分割成兩個相等的子集
            if (target == 0) return (dp[idx][target] = true).value();

            // 遞歸情況：嘗試包含當前數字在子集內並遞歸
            // 如果包含索引`idx`處的當前數字仍然允許有效分割
            if (target - nums[idx] >= 0 && canPartition(nums, idx + 1, target - nums[idx])) {
                return (dp[idx][target] = true).value();
            }

            // 遞歸情況：嘗試不包含當前數字並遞歸
            return (dp[idx][target] = canPartition(nums, idx + 1, target)).value();
        }
    }
};

Python

class Solution:
    # 宣告一個二維列表用於記憶化儲存中間結果
    dp = []

    def canPartition(self, nums, idx=-1, target=-1):
        # 初始呼叫設置
        if idx == -1:
            # 計算數組元素的總和
            target = sum(nums)

            # 如果總和是奇數，則不可能分割成等和子集
            if target & 1:
                return False

            # 每個子集的期望和為總和的一半
            target //= 2

            # 清空並重新調整 dp 列表的大小，根據當前的 nums 大小和目標和
            self.dp = [[None] * (target + 1) for _ in range(len(nums))]

            # 從索引 0 開始遞歸搜尋
            return self.canPartition(nums, 0, target)
        else:
            # 基本情況：所有元素都已考慮，如果未達到目標則返回 false
            if idx >= len(nums):
                return False

            # 如果這個子問題已經解決，則返回存儲的結果
            if self.dp[idx][target] is not None:
                return self.dp[idx][target]

            # 如果目標和為零，我們已成功分割成兩個等和子集
            if target == 0:
                self.dp[idx][target] = True
                return True

            # 遞歸情況：嘗試將當前數字包含在子集中並遞歸
            # 如果包含在索引 `idx` 的當前數字後仍能有效分割
            if target - nums[idx] >= 0 and self.canPartition(nums, idx + 1, target - nums[idx]):
                self.dp[idx][target] = True
                return True

            # 遞歸情況：嘗試將當前數字排除並遞歸
            self.dp[idx][target] = self.canPartition(nums, idx + 1, target)
            return self.dp[idx][target]

複雜度分析

時間複雜度: 給定演算法的時間複雜度為 $O(n \cdot m)$，其中 $n$ 是輸入陣列 nums 中的元素數量，$m$ 是目標和，它是陣列總和的一半。在最壞情況下，我們需要為每個元素探索每一個到達目標和的子集合可能性。使用記憶化技術減少了重複計算。
空間複雜度: 空間複雜度為 $O(n \cdot m)$，因為使用了一個二維向量 dp 來儲存 n 個元素和可能的和到 $m$ 的中間結果。此外，遞歸的呼叫堆疊最多可以增長到 $O(n)$，但在考慮 dp 向量時，這並不影響漸進的空間複雜度。

CS Note
En

Leetcode 416. Partition Equal Subset Sum

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析