Partition Equal Subset Sum

Try to solve the Partition Equal Subset Sum problem.

We'll cover the following

Statement#

Given a non-empty array of positive integers, determine if the array can be divided into two subsets so that the sum of both subsets is equal.

Constraints:

  • 1≤1 \leq nums.length ≤200\leq 200
  • 1≤1 \leq nums[i] ≤100\leq 100

Examples#

Created with Fabric.js 3.6.6 Input Sample example 1 1 3 7 3 TRUE The array can be partitioned as: [1, 3, 3] and [7].

1 of 4

Created with Fabric.js 3.6.6 Input 1 2 5 The array can not be partitioned as needed. FALSE Sample example 2

2 of 4

Created with Fabric.js 3.6.6 1 2 3 11 5 Input Sample example 3 TRUE The array can be partitioned as: [1, 2, 3, 5] and [11].

3 of 4

Created with Fabric.js 3.6.6 Input 1 6 20 7 8 Sample example 4 TRUE The array can be partitioned as: [1, 20] and [6, 7, 8].

4 of 4

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Partition Equal Subset Sum

1

What is the output if the array [1, 2, 5, 2] is given as input?

A)

TRUE

B)

FALSE

Question 1 of 40 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Create a matrix of appropriate size and initialize all cells with FALSE.

Place TRUE in the first row of the matrix.

Traverse the input array, element by element.

Fill the cells of matrix either TRUE or FALSE depending upon their inclusion in the subset sum.

The value present at the last row and last column indicates whether the array can be partitioned.

Try it yourself#

Implement your solution in the following coding playground:

Python
usercode > main.py
Input #1
%0 node_01 3 node_11 1 node_21 1 node_31 2 node_41 2 node_51 1
Visualization for Input #1
Partition Equal Subset Sum

Solution: Longest Palindromic Substring

Solution: Partition Equal Subset Sum