Created
April 18, 2021 23:33
-
-
Save humpydonkey/6e1652f1b5486cd185073a103cc6ed2a to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
// We maintain a 2D array , dp[n][subSetSum] | |
// For an array element i and sum j in array nums, | |
// dp[i][j]=true if the sum j can be formed by array elements | |
// in subset nums[0]..nums[i], otherwise dp[i][j]=false | |
// | |
// Time: O(n * sum) | |
// Space: O(n * sum) | |
public boolean canPartition(int[] nums) { | |
int totalSum = Arrays.stream(nums).sum(); | |
if (totalSum % 2 != 0) | |
return false; | |
boolean[][] dp = new boolean[nums.length+1][totalSum / 2 + 1]; | |
dp[0][0] = true; | |
int prefixSum = 0; | |
for (int i = 1; i < nums.length + 1; i++) { | |
int num = nums[i-1]; | |
prefixSum += num; | |
for (int j = 0; j < dp[0].length; j++) { | |
if (dp[i-1][j] || (j-num >= 0 && dp[i-1][j-num])) { | |
dp[i][j] = true; | |
} | |
} | |
} | |
return dp[nums.length][dp[0].length - 1]; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment