Solving Partition Equal Subset Sum Problem — Knapsack problem

In this post, we will look the dynamic programming problem which falls into the category of Knapsack problems.

In this post, let’s tackle an interesting problem — the “Partition Equal Subset Sum” problem (Leetcode 416). We’ll start with a straightforward solution, and gradually evolve it into a super-efficient one using a fascinating technique called Dynamic Programming. Let’s dive in!

Deciphering the Problem

Given an array nums that contains only positive integers, can we split the array into two subsets so that the sum of elements in both subsets is equal?

For example, consider nums = [1,5,11,5], the array can be partitioned as [1, 5, 5] and [11], so the output should be true.

The Starting Point: Brute Force Solution

The most straightforward, or ‘brute force’, approach to this problem is to try all possible subsets and check if there’s a pair of subsets that sums to the same value.

Let’s see how we could implement this in Java:

public class Solution {
    public boolean canPartition(int[] nums) {
        // Calculate the sum of all elements in the array
        int total = 0;
        for(int i: nums) {…