Given an integer array nums, return trueif you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.
Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
Constraints:
1 <= nums.length <= 200
1 <= nums[i] <= 100
Solutions
Solution 1: Dynamic Programming
First, we calculate the total sum $s$ of the array. If the total sum is odd, it cannot be divided into two subsets with equal sums, so we directly return false. If the total sum is even, we set the target subset sum to $m = \frac{s}{2}$. The problem is then transformed into: does there exist a subset whose element sum is $m$?
We define $f[i][j]$ to represent whether it is possible to select several numbers from the first $i$ numbers so that their sum is exactly $j$. Initially, $f[0][0] = true$ and the rest $f[i][j] = false$. The answer is $f[n][m]$.
Considering $f[i][j]$, if we select the $i$-th number $x$, then $f[i][j] = f[i - 1][j - x]$. If we do not select the $i$-th number $x$, then $f[i][j] = f[i - 1][j]$. Therefore, the state transition equation is:
$$
f[i][j] = f[i - 1][j] \textit{ or } f[i - 1][j - x] \textit{ if } j \geq x
$$
The final answer is $f[n][m]$.
The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Where $m$ and $n$ are half of the total sum of the array and the length of the array, respectively.
classSolution{publicbooleancanPartition(int[]nums){// int s = Arrays.stream(nums).sum();ints=0;for(intx:nums){s+=x;}if(s%2==1){returnfalse;}intn=nums.length;intm=s>>1;boolean[][]f=newboolean[n+1][m+1];f[0][0]=true;for(inti=1;i<=n;++i){intx=nums[i-1];for(intj=0;j<=m;++j){f[i][j]=f[i-1][j]||(j>=x&&f[i-1][j-x]);}}returnf[n][m];}}
implSolution{#[allow(dead_code)]pubfncan_partition(nums:Vec<i32>)->bool{letmutsum=0;forein&nums{sum+=*e;}ifsum%2!=0{returnfalse;}letn=nums.len();letm=(sum/2)asusize;letmutdp:Vec<Vec<bool>>=vec![vec![false;m+1];n+1];// Initialize the dp vectordp[0][0]=true;// Begin the actual dp processforiin1..=n{forjin0..=m{dp[i][j]=if(nums[i-1]asusize)>j{dp[i-1][j]}else{dp[i-1][j]||dp[i-1][j-(nums[i-1]asusize)]};}}dp[n][m]}}
We notice that in Solution 1, $f[i][j]$ is only related to $f[i - 1][\cdot]$. Therefore, we can compress the two-dimensional array into a one-dimensional array.
The time complexity is $O(n \times m)$, and the space complexity is $O(m)$. Where $n$ is the length of the array, and $m$ is half of the total sum of the array.
classSolution{publicbooleancanPartition(int[]nums){// int s = Arrays.stream(nums).sum();ints=0;for(intx:nums){s+=x;}if(s%2==1){returnfalse;}intm=s>>1;boolean[]f=newboolean[m+1];f[0]=true;for(intx:nums){for(intj=m;j>=x;--j){f[j]|=f[j-x];}}returnf[m];}}
implSolution{#[allow(dead_code)]pubfncan_partition(nums:Vec<i32>)->bool{letmutsum=0;forein&nums{sum+=*e;}ifsum%2!=0{returnfalse;}letm=(sum>>1)asusize;// Here dp[i] means if it can be sum up to `i` for all the number we've traversed through so far// Which is actually compressing the 2-D dp vector to 1-Dletmutdp:Vec<bool>=vec![false;m+1];// Initialize the dp vectordp[0]=true;// Begin the actual dp processforein&nums{// For every num in nums vectorforiin(*easusize..=m).rev(){// Update the current statusdp[i]|=dp[i-(*easusize)];}}dp[m]}}