416. Partition Equal Subset Sum
Problem Description
The given problem asks us to determine if we can split an array of integers, nums
, into two subsets such that the sum of the elements in both subsets is the same. This is essentially asking if nums
can be partitioned into two subsets of equal sum. If such a partition is possible, we should return true
, otherwise, we return false
.
To understand this problem better, imagine you have a set of blocks with different weights, and you want to see if you can divide them into two groups that weigh the same. If it can be done, then each group represents a subset with an equal sum.
Intuition
The solution to this problem is based on the concept of dynamic programming, particularly the 0/1 Knapsack problem, where we aim to find a subset of numbers that can sum up to a specific target, in this case, half the sum of all elements in nums
.
The intuition behind this solution is:
-
First, we calculate the sum of all elements in the array. If the sum is an odd number, it's impossible to partition the array into two subsets with an equal sum, so we immediately return
false
. -
If the sum is even, our target becomes half of the total sum, and we set up an array
f
of boolean values that represents if this sum can be reached using a combination of the numbers weāve seen so far.f
is initialized with a size equal to the target plus one (m + 1
), with the first valueTrue
(since we can always reach a sum of 0) and the restFalse
. -
We iterate over each number in our array
nums
. For each number, we update ourf
array from right to left, starting at our targetm
and going down to the value of the numberx
. We do this backward to ensure that each number is only considered once. At each positionj
, we updatef[j]
by checking iff[j]
was previously true or iff[j-x]
was true. The latter means that if we already could sum up toj-x
, then by addingx
, we can now also sum up toj
. -
At the end of this process,
f[m]
tells us whether we've found a subset of elements that sum up tom
, which would be half the sum of the entire array. Iff[m]
is true, we have our partition and returntrue
, otherwise, we returnfalse
.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution implements a classic dynamic programming approach to solve the subset sum problem, which is a variation of the 0/1 Knapsack problem. Here's a step-by-step guide to understanding the algorithm:
-
Calculate the Sum and Determine Feasibility: We begin by finding the sum of all elements in the array using
sum(nums)
. We divide this sum by 2 using thedivmod
function, which gives us the quotientm
and the remaindermod
. Ifmod
is not zero, the sum is odd, and we cannot partition an odd sum into two equal even halves, so we returnfalse
. -
Dynamic Programming Array Setup: Next, we set up an array
f
withm + 1
boolean elements, which will help us track which sums can be achieved from subsets of the array. We initializef[0]
toTrue
because a zero sum is always possible (the empty subset), and the rest toFalse
. -
Iterate and Update the DP Array: For each number
x
innums
, we iterate over the arrayf
fromm
down tox
. We do this in reverse order to ensure that each element contributes only once to each sum. -
Update the DP Array: For each position
j
inf
, we check iff[j]
was alreadyTrue
(sumj
was already achievable) or iff[j - x]
wasTrue
. Iff[j - x]
wasTrue
, it means there was a subset of previous elements that added up toj - x
. By including the current elementx
, we can now reach the sumj
, so we setf[j]
toTrue
. -
Return the Result: Finally, we return the value of
f[m]
. This value tells us whether there is a subset of elements fromnums
that adds up tom
, which would be half of the total sum. Iff[m]
isTrue
, it means we can partition the array into two subsets with an equal sum, and we returntrue
; otherwise, we returnfalse
.
The pattern used in this algorithm leverages the properties of boolean arithmetic wherein True
represents 1 and False
represents 0. The statement f[j] = f[j] or f[j - x]
is an efficient way to update our boolean array because it captures both conditions for setting f[j]
to True
: either it's already True
, or f[j - x]
is True
and we just add x
to reach the required sum j
.
By re-using the array f
in each iteration and only considering each number once, we keep our space complexity to O(sum/2), which is much more efficient than trying to store all possible subset sums up to the total sum of the array.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach. Consider an array nums
with the following elements: [1, 5, 11, 5]
.
-
Calculate the Sum and Determine Feasibility:
- Compute the sum of the elements:
1 + 5 + 11 + 5 = 22
. - Use
divmod
to check if the sum is even or odd:divmod(22, 2)
gives us(11, 0)
. - Since the remainder is
0
, the sum is even, and proceeding is feasible.
- Compute the sum of the elements:
-
Dynamic Programming Array Setup:
- Our target sum
m
is22 / 2 = 11
. - Initialize
f
with dimensions[12]
(m + 1
) and setf[0]
toTrue
.
- Our target sum
-
Iterate and Update the DP Array:
- Start iterating over the array
nums
:[1, 5, 11, 5]
.
- Start iterating over the array
-
Update the DP Array:
- For
x
= 1 (first element), updatef
from11
down to1
. Sincef[0]
isTrue
, setf[1]
toTrue
. - For
x
= 5 (second element), updatef
from11
down to5
. Nowf[5]
,f[6]
,f[7]
,f[8]
,f[9]
, andf[11]
becomeTrue
. - For
x
= 11 (third element), sincef[0]
isTrue
, setf[11]
toTrue
. However,f[11]
is alreadyTrue
from the previous step. - Lastly, for
x
= 5 (fourth element), updatef
again similarly to whenx
was5
before.
- For
-
Return the Result:
- After the final iteration, we check the value of
f[11]
, which isTrue
. - This indicates that there is a subset with a sum of
11
, which is half of the total sum.
- After the final iteration, we check the value of
Therefore, the array [1, 5, 11, 5]
can be partitioned into two subsets with equal sum, and we return true
.
Solution Implementation
1class Solution:
2 def can_partition(self, nums: List[int]) -> bool:
3 # Compute the total sum of the nums array and divide by 2 (partition sum)
4 total_sum, remainder = divmod(sum(nums), 2)
5
6 # If the sum of nums is odd, we cannot partition it into two equal subsets
7 if remainder:
8 return False
9
10 # Initialize a boolean array that will keep track of possible sums
11 can_partition = [True] + [False] * total_sum
12
13 # Loop through each number in the nums array
14 for num in nums:
15 # Check each possible sum in reverse (to avoid using the same number twice)
16 for j in range(total_sum, num - 1, -1):
17 # Update the can_partition array
18 # True if the number itself can form the sum
19 # or if the sum can be formed by adding the number to a previously possible sum
20 can_partition[j] = can_partition[j] or can_partition[j - num]
21
22 # The last element in the can_partition array indicates if we can partition
23 # nums into two equal subsets
24 return can_partition[total_sum]
25
1class Solution {
2 public boolean canPartition(int[] nums) {
3 // Calculate the sum of all array elements
4 int sum = 0;
5 for (int num : nums) {
6 sum += num;
7 }
8
9 // If the sum is odd, it's not possible to partition the array into two subsets of equal sum
10 if (sum % 2 != 0) {
11 return false;
12 }
13
14 // Target sum for each subset is half of the total sum
15 int targetSum = sum / 2;
16
17 // Create a boolean array to store the subset sums achievable up to the targetSum
18 boolean[] subsetSums = new boolean[targetSum + 1];
19
20 // There's always one subset with sum 0, the empty set
21 subsetSums[0] = true;
22
23 // Check each number in the given array
24 for (int num : nums) {
25 // Traverse the subsetSums array in reverse to avoid using an element multiple times
26 for (int j = targetSum; j >= num; j--) {
27 // Update the subset sums that are achievable
28 // If j-num is achievable, set j as achievable (because we're adding num to the subset)
29 subsetSums[j] = subsetSums[j] || subsetSums[j - num];
30 }
31 }
32
33 // The result is whether the targetSum is achievable as a subset sum
34 return subsetSums[targetSum];
35 }
36}
37
1#include <numeric>
2#include <vector>
3#include <cstring>
4
5class Solution {
6public:
7 // Function to determine if the input array can be partitioned into two subsets of equal sum
8 bool canPartition(vector<int>& nums) {
9 // Calculate the sum of elements in the nums array
10 int totalSum = accumulate(nums.begin(), nums.end(), 0);
11
12 // If the total sum is odd, it's not possible to divide it into two equal parts
13 if (totalSum % 2 == 1) {
14 return false;
15 }
16
17 // Target sum for each partition
18 int targetSum = totalSum >> 1;
19
20 // Create a dynamic programming array to keep track of possible sums
21 bool dp[targetSum + 1];
22
23 // Initialize the dynamic programming array to false
24 memset(dp, false, sizeof(dp));
25
26 // The sum of 0 is always achievable (by selecting no elements)
27 dp[0] = true;
28
29 // Iterate through the numbers in the array
30 for (int num : nums) {
31 // Check each possible sum in reverse to avoid using a number twice
32 for (int j = targetSum; j >= num; --j) {
33 // Update the dp array: dp[j] will be true if dp[j - num] was true
34 // This means that current number 'num' can add up to 'j' using the previous numbers
35 dp[j] = dp[j] || dp[j - num];
36 }
37 }
38
39 // The result is whether it's possible to achieve the targetSum using the array elements
40 return dp[targetSum];
41 }
42};
43
1function canPartition(nums: number[]): boolean {
2 // Calculate the sum of all elements in the array
3 const totalSum = nums.reduce((accumulator, currentValue) => accumulator + currentValue, 0);
4
5 // If the total sum is odd, it's not possible to partition the array into two subsets with an equal sum
6 if (totalSum % 2 !== 0) {
7 return false;
8 }
9
10 // Target sum is half of the total sum
11 const targetSum = totalSum >> 1;
12
13 // Initialize a boolean array to keep track of possible subset sums
14 const possibleSums = Array(targetSum + 1).fill(false);
15 // Always possible to pick a subset with sum 0 (empty subset)
16 possibleSums[0] = true;
17
18 // Iterate through all numbers in the given array
19 for (const num of nums) {
20 // Iterate backwards through possibleSums array to check if current number can contribute to the targetSum
21 for (let j = targetSum; j >= num; --j) {
22 // Update possibleSums array to reflect the new subset sum that can be formed
23 possibleSums[j] = possibleSums[j] || possibleSums[j - num];
24 }
25 }
26
27 // Return whether a subset with the targetSum is possible
28 return possibleSums[targetSum];
29}
30
Time and Space Complexity
The code is designed to solve the Partition Equal Subset Sum problem which is to determine if the given set of numbers can be partitioned into two subsets such that the sum of elements in both subsets is the same.
Time Complexity
The time complexity is O(n * m)
where n
is the number of elements in nums
and m
is half the sum of all elements in nums
if the sum is even. This complexity arises from the double loop structure: an outer loop iterating over each number x
in nums
, and an inner loop iterating backwards from m
to x
. The inner loop runs at most m
iterations (representing the possible sums up to half the total sum), and this is done for each of the n
numbers.
Space Complexity
The space complexity is O(m)
where m
is half the sum of all elements in nums
(if the sum is even). This is due to the array f
, which stores Boolean values indicating whether a certain sum can be reached with the current subset of numbers. The array f
has a length of m + 1
, with m
being the target sum (the zero is included to represent the empty subset).
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!