Eisen 筆記

#416. Partition Equal Subset Sum

題目描述

給你一個整數陣列nums，如果你可以拆分陣列變成兩個區塊並且各自陣列中元素的和是相等的則回傳true，反之回傳false。

限制條件

  1. 1 <= nums.length <= 200
  2. 1 <= nums[i] <= 100

解題思路

Dynamic Programming

直覺地來說，我們知道只要將陣列中的數值總和的組合都試過一次，如果其中有組合的總和等於陣列總和的一半，那麼這個陣列就可以拆成兩個相等的區塊。

舉例來說：
可拆分：nums = [1,5,11,5], sum = 1+5+11+5 = 22, sum/2 = 11 = 1+5+5
不可拆分：nums = [1,4,12,5], sum = 1+4+12+5 = 22, sum/2 = 11\

從上面兩個例子可以很清楚的看到我們的目標就是陣列中必須存在總和等於sum/2的組合。

最簡單的解法就是窮舉出所有的排列組合，但是肯定會耗費大量時間導致超時。

要降低排列組合的時間，最好的方式就是將曾經的組合結果記錄下來，並且在過去的結果上排列新的組合。 而每個排列組合都可以視為是一個獨立的結果，因此滿足了動態規劃的條件。

動態規劃的策略列舉了總和sum(i)和數值nums[i]的組合，如下：\

假設數值為nums = [1,5,11,5]，總和為sum = 22，動態規劃表為：

sum(i)012345678910111213141516171819202122
1TT
5TTT
11TTTTT
5TTTTTTTTT
numsTTTTTTTTTT

當沒有總和為0的時候也就是sum(0)，是可以完成的組合，因此為true。
接著來看數值nums[0] = 1，當總和為1的時候sum(1) = sum(0 + 1) = true，其餘總和無法達成所以為false。

接著看數值nums[1] = 5，會有2個結果：

  • 當總和為5的時候sum(5) = sum(0 + 5) = true
  • 當總和為6的時候sum(6) = sum(1 + 5) = true，sum(1)是上一個數值所留下的結果。

接著看數值nums[2] = 11，會有4個結果：

  • 當總和為5的時候sum(11) = sum(0 + 11) = true
  • 當總和為6的時候sum(12) = sum(1 + 11) = true，sum(1)是上上一個數值所留下的結果。
  • 當總和為5的時候sum(16) = sum(5 + 11) = true，sum(5)是上一個數值所留下的結果。
  • 當總和為6的時候sum(17) = sum(6 + 11) = true，sum(6)是上一個數值所留下的結果。

接著看數值nums[2] = 11，會9個結果：

  • 當總和為5的時候sum(5) = sum(0 + 5) = true
  • 當總和為6的時候sum(6) = sum(1 + 5) = true
  • 當總和為10的時候sum(10) = sum(5 + 5) = true
  • 當總和為11的時候sum(11) = sum(6 + 5) = true
  • 當總和為16的時候sum(16) = sum(11 + 5) = true
  • 當總和為17的時候sum(17) = sum(12 + 5) = true
  • 當總和為21的時候sum(21) = sum(16 + 5) = true
  • 當總和為22的時候sum(22) = sum(17 + 5) = true

而所有數值之間的排列組合會有10種結果，而我們目標值就是sum/2 = 11 = sum(11)存在於結果之中，因此這個例子是可以被拆分成兩個區間的。

程式碼的步驟如下：

  1. 加總所有數值sum。
  2. 如果sum不是偶數，則無法拆分成兩個相等的數值，因此也不需要繼續往下執行。
  3. 建立dp表格，表格長度為sum + 1，[0, sum]。
  4. 計算每個數值的排列組合結果，由後往前算。
    • 由後往前算才能得到結果，假設由前往後算的話，會發生重複使用的狀況，以sum(1)為例，sum(0) = true = sum(1) = sum(2) = ... = sum(i)，但是我們的目的是每個元素只能使用一次，因此不能由前往後算。
    • dp[i] = dp[i] || dp[ i - nums[n] ]，等號右邊的dp[i]是上一輪數值的結果，dp[ i - nums[n] ]是往前查詢結果是否有排列組合的結果存在作為判斷新的組合是否成立。
  5. 回傳dp[sum/2]，如果中間值的結果存在，則陣列可以拆分成兩個分區並且分區數值會相等，達成題目要求。
public class Solution {
    public bool CanPartition(int[] nums) {
        int sum = 0;
        foreach(var i in nums) sum+=i;        
        if(sum%2!=0) return false;        
        
        var dp = new bool[sum+1];
        dp[0] = true;
                
        for(int n=0;n<nums.Length;n++){                    
            for(int i=sum;i>=nums[n];i--){
                dp[i] = dp[i] || dp[ i - nums[n] ];
            }
        }        

        return dp[sum/2];
    }
}

複雜度分析：

  • 時間複雜度：我們需要計算所有DP表格的結果，DP表格的大小(sum+1) * nums.Length，因此時間複雜度為( n * m )，n為sum + 1，m為nums.Length。
  • 空間複雜度：DP表格的展開是(sum+1) * nums.Length，但是過去的結果可以直接被存在DP之中，因此表格可以被壓縮成一列，長度為[0,sum]，所以空間複雜度為O(n)，n為sum + 1。

學習重點

  • Dynamic Programming
Last Updated:
Contributors: eisen