Problem
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:
Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].Example 2:
Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.Constraints:
・ 1 <= nums.length <= 200 ・ 1 <= nums[i] <= 100
Idea
주어진 배열이 동일한 합을 가진 subarray 두 개로 나눠지는지 확인하는 문제다. 못 풀다가 Discussion의 풀이를 보고 이해를 했다.
우선 배열의 합을 구하고 2로 나눈 나머지가 0이 아니면 false를 리턴한다.
다음으로 dp를 만드는데, dp는 배열의 index를 기준으로 값이 만들어질 수 있는지 여부를 확인한다. 그래서 2-d array로 배열을 만들고 행은 배열의 크기, 열은 값으로 정한다. 해당 index까지 값을 기준으로 값을 만들 수 있는지 여부를 저장하는 boolean array가 바로 dp다.
배열을 탐색하면서 우선 행이나 열이 0이면 false로 설정을 한다. 이는 이전 dp를 탐색하여 값을 만들지 여부를 결정해야 되기 때문이기도 하고, 0을 만들 수 없기 때문이기도 하다.
만약 배열의 값이 j보다 크다면 이전 dp에서 j를 만들 수 있는지 여부를 그대로 설정한다. 단지 현재 index의 값을 사용하지 않으면 j값을 만들 수 있기 때문이다.
현재 배열의 값이 j와 같다면, 현재 배열의 값만 이용해 j를 만들 수 있다는 뜻이므로 그대로 true로 설정한다.
그 외의 경우는 이전 dp값이 true이거나 이전 dp값에서 j에서 현재 값을 뺀 값이 true로 설정되어 있으면 dp 값도 true로 설정된다. 이는 이전 배열에서 (j - 현재값)을 만들 수 있다면 현재값을 더하는 것으로 j를 만들 수 있기 때문이다.
모든 dp를 탐색한 뒤 마지막 index 값을 리턴하면 된다.
Solution
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
int sum = 0;
for (int i : nums)
sum += i;
if (sum % 2 != 0)
return false;
int half = sum / 2;
boolean[][] dp = new boolean[n+1][half+1];
for (int i=0; i <= n; i++) {
for (int j=0; j <= half; j++) {
if (i == 0 || j == 0)
dp[i][j] = false;
else if (nums[i-1] > j)
dp[i][j] = dp[i-1][j];
else if (nums[i-1] == j)
dp[i][j] = true;
else
dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]];
}
}
return dp[n][half];
}
}Reference
