题目

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

  1. Input: nums = [1,5,11,5]
  2. Output: true
  3. Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

  1. Input: nums = [1,2,3,5]
  2. Output: false
  3. Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

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

题意

在一个给定数组中找到一个子数组，使其和为指定值。

思路

使用记忆化搜索容易实现。

代码实现

Java

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         int total = 0;
  4.         int left = 0, right = nums.length - 1;
  6.         for (int num : nums) {
  7.             total += num;
  8.         }
  10.         if (total % 2 == 1) {
  11.             return false;
  12.         }
  14.         return dfs(total / 2, nums, 0, new Boolean[total / 2 + 1][nums.length]);
  15.     }
  17.     private boolean dfs(int sum, int[] nums, int start, Boolean[][] record) {
  18.         if (start == nums.length) {
  19.             return sum == 0;
  20.         }
  21.         if (sum < 0) {
  22.             return false;
  23.         }
  24.         if (record[sum][start] != null) {
  25.             return record[sum][start];
  26.         }
  28.         boolean found = dfs(sum, nums, start + 1, record) || dfs(sum - nums[start], nums, start + 1, record);
  29.         record[sum][start] = found;
  30.         return found;
  31.     }
  32. }