Partition Equal Subset Sum
DP on Subsequences DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Partition Equal Subset Sum Problem: Can an integer array be divided into two subsets with equal sum?, Dynamic Programming, Memoization, Tabulation, Space Optimization, Subsequences, Recursion, Arrays, Time Complexity, Space Complexity, Basic Arithmetic, Conditional Statements, Loops, dynamic programming, recursion with memoization, divide and conquer, tabulation, array traversal, dynamic programming optimization.
Partition Equal Subset Sum Given a non empty array ARR containing N positive integers. Determine if it is possible to partition the array into two subsets such that the sum of elements in both subsets is equal. If such a partition is possible, return true. Otherwise, return false. Input Specification: The first line of input contains an integer N, representing the number of elements in the array. The second line contains N space separated positive integers, representing the elements of ARR. Output Specification: Return true if the array can be partitioned into two equal subsets, otherwise return false. Example: Input: 6 2 3 3 3 4 5 Output: true Explanation: Total sum of elements in ARR is 20. If it can be partitioned into two equal subsets, each subset must sum to 10. One possible partition: Subset 1 = {2, 3, 5} (sum = 10), Subset 2 = {3, 3, 4} (sum = 10). Since we found two subsets with equal sum, the output is true.