Partition equal subset sum

Array Dynamic Programming

49.2% acceptance

Jan 13, 2026

13777

298

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn can_partition(nums: Vec<i32>) -> bool {
    let sum: i32 = nums.iter().sum();
    if sum % 2 != 0 {
      return false;
    }
    
    let target = sum / 2;
    let mut dp = vec![false; target as usize + 1];
    dp[0] = true;
    
    for num in nums {
      for i in (num as usize..=target as usize).rev() {
        dp[i] = dp[i] || dp[i - num as usize];
      }
    }
    
    dp[target as usize]
  }
}