力扣416——分割等和子集頭條網

2021-03-28 02:59:17 佚名

這道題主要涉及的是動態規劃，類似揹包問題，主要還是需要找出狀態轉移方程，優化時可以考慮採用深度優先搜索。

原題

給定一個只包含正整數的非空數組。是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。

注意:

每個數組中的元素不會超過 100
數組的大小不會超過 200

示例 1:

<code>輸入:
 [1,
 5
,
 11
,
 5
]

輸出:
 true

解釋:
 數組可以分割成
 [1,
  
5
,
 5
]
 和
 [11].
 ```

示例
 2:
/<code>

輸入: [1, 2, 3, 5]

輸出: false

解釋: 數組不能分割成兩個元素和相等的子集.

<code>
原題url：https://leetcode-cn.com/problems/partition-equal-subset-sum/

## 解題

### 動態規劃

針對這種問題，動態規劃是最直接的思路。針對每一個數字，你都有兩個選擇：選、不選。我們的目標是為了讓選出來的數字之和等於所有數字之和的一半。

這和`0-1 揹包問題`
很類似，我們可以利用二維表格 dp 解決，表格有`len`
行、`target+1`
列，這裡`len` 
表示當前數字所處的數組下標，`target`
表示所有數字之和(最大值為：所有數字之和的一半)，`target+1`是表明數字之和從0開始。

接下來考慮`狀態定義`
和`狀態轉移方程`：

狀態定義：`dp[i][j]`表示從原始數組的 [0, i] 這個子區間內挑選一些數，每個數只能用一次，使得這些數的和恰好等於 j。

狀態轉移方程：對於“0-1 揹包問題”，就是考慮數字是否選擇。
1. 
不選擇 nums[i
]，如果在 [0, i - 1
] 這個子區間內已經有一部分元素，使得它們的和為 j ，那麼 dp[i
][j] = true；
2. 
選擇 nums[i
]，如果在 [0, i - 1
] 這個子區間內就得找到一部分元素，使得它們的和為 j - nums[i
]，那麼 dp[i 
][j] = true；
3. 
其餘情況，dp[i
][j] = false；

所以狀態轉移方程是：`dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]`

接下來我們看看代碼：/<code>

public class Solution {

<code>    
public
 boolean
 canPartition
(
int[] nums) {
        int len = nums.length;
        if
 (len == 0) {
            return
 false;
        }/<code>

<code>         
        int
 sum = 0;
        for
 (int num : nums) {
            sum += num;
        }/<code>

<code>         
         
if
 ((sum & 1
) == 1) {
            return
 false;
        }
         
        int
 target = sum / 2;
         
        boolean
[][] dp = new
 boolean
[len][target + 1
];/<code>

<code>        //
 先填表格第
 0
 行，第
 1
 個數只能讓容積為它自己的揹包恰好裝滿
        if
 (nums[0]
 
 target)
 {
            dp[0][nums[0]]
  
=
 true
;
        }
/<code>

<code>         
        for
 (int
 i = 1
; i len; i++) {
            for
 (int
 j = 0; j <= target; j++) {
                 
                if
 (dp[i - 1][j] ||
                     
                    nums[i] == j ||
                     
                    (nums[i] < j && dp[i - 1][j - nums[i]])) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = false;
                }
            }
        }
        return
 dp[len
 - 1][target];
    }
}
``
`
提交OK。
/<code>

動態規劃——優化

時間上的優化，其實可以提前結束，只要滿足 target，就滿足了總和一半的條件，可以直接結束，並不需要全部算完。

空間上的優化，其實只需要一維即可，因為只用了上一次的所有情況，並不需要所有。

接下來我們看看代碼：

<code>public
 
class
 Solution {

    
public
 boolean
 canPartition
(
int[] nums) {
        int len = nums.length;
        if
 (len == 0) {
            return
 false;
        }
                
         
        int
 sum = 0;
        for 
 (int num : nums) {
            sum += num;
        }

         
        if
 ((sum & 1
) == 1) {
            return
 false;
        }
         
        int
 target = sum / 2;
         
        boolean
[] dp = new
 boolean
[target + 1];
        dp[0
] = true;
         
        if
 (nums[0] <= target) {
            dp[nums[0
]] = true;
        }

         
        for
 (int
 i = 1; i < len; i++) {
            for
 (int j = target; nums[i] <= j; j--) {
                 
if (dp[target]) {
                    return
 true;
                }

                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}/<code>

提交OK。

深度優先搜索

和動態規劃類似，只是換成了遞歸的寫法。

針對一個數字選還是不選的問題，要求選擇的數字之和達到一半，等價於不選擇的數字之和也達到了一半。

只是針對剪枝，需要提供更多一些的情況：可以先從小到大排序，然後從大的一方開始找，這樣可以快速失敗，因為當超過一半之後，可以直接結束。

接下來看看代碼：

<code>
class
 Solution {
    
public
 boolean
 canPartition
(
 
int[] nums) {
         
        int
 sum = 0;
        for
 (int num : nums) {
            sum += num;
        }
         
        if
 ((sum & 1
) == 1) {
            return
 false;
        }
         
        sum = sum >> 1;

         
        Arrays.sort(nums);
         
        return
 canPartition(nums, nums.length - 1, sum, sum);
    }

    
public
 boolean
 canPartition
(
        
int[] nums,
        int index,
        int canIncrease,
        int canDecrease) {
         
        if
 (canIncrease == 0
 || canDecrease == 0) {
            return 
 true;
        }

         
        if
 (canIncrease 0
 || canDecrease 0) {
            return
 false;
        }

         
        if
 (index 0) {
            return
 false;
        }
         
        return
 canPartition(nums, index - 1, canIncrease - nums[index], canDecrease) ||
            canPartition(nums, index - 1, canIncrease, canDecrease - nums[index]);
    }
}/<code>