educative.io

Can we solve this problem too with Space complexity of O(n) like the Knapsack problem?

Courses
,
#1

Can we solve this problem too with Space complexity of O(n) like the Knapsack problem?

#2

boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 == 1) {
return false;
}
sum = sum >>> 1;

    boolean dp[] = new boolean[sum + 1];
    dp[0] = true;

    for (int num : nums) {
        for(int s = sum; s >= 0; s--) {
            if (s >= num) {
                dp[s] = dp[s - num];
            }
        }
    }
    return dp[sum];
}