Partition Equal Subset Sum

                                            
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        if (sum % 2 != 0) {
            return false;
        }
        
        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        
        return dp[target];
    }
};

                                            
class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        if (totalSum % 2 != 0) {
            return false;
        }
        
        int target = totalSum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        
        return dp[target];
    }
}

                                            
class Solution(object):
    def canPartition(self, nums):
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        
        half_sum = total_sum // 2
        dp = [False] * (half_sum + 1)
        dp[0] = True
        
        for num in nums:
            for i in range(half_sum, num - 1, -1):
                dp[i] = dp[i] or dp[i - num]
        
        return dp[half_sum]

                                            
bool canPartition(int* nums, int numsSize) {
    int totalSum = 0;
    for (int i = 0; i < numsSize; i++) {
        totalSum += nums[i];
    }
    if (totalSum % 2 != 0) {
        return false;
    }

    int target = totalSum / 2;
    bool dp[target + 1];
    memset(dp, false, sizeof(dp));
    dp[0] = true;

    for (int i = 0; i < numsSize; i++) {
        for (int j = target; j >= nums[i]; j--) {
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }

    return dp[target];
}

                                            
public class Solution {
    public bool CanPartition(int[] nums) {
        int sum = 0;
        foreach (int num in nums) {
            sum += num;
        }
        
        if (sum % 2 != 0) {
            return false;
        }
        
        int target = sum / 2;
        bool[] dp = new bool[target + 1];
        dp[0] = true;
        
        foreach (int num in nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        
        return dp[target];
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {boolean}
 */
const canPartition = function(nums) {
    const sum = nums.reduce((a, b) => a + b, 0);
    if (sum % 2 !== 0) {
        return false;
    }
    
    const target = sum / 2;
    const dp = new Array(target + 1).fill(false);
    dp[0] = true;
    
    for (const num of nums) {
        for (let i = target; i >= num; i--) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    
    return dp[target];
};

                                            
function canPartition(nums: number[]): boolean {
    const totalSum = nums.reduce((a, b) => a + b, 0);

    if (totalSum % 2 !== 0) {
        return false;
    }

    const targetSum = totalSum / 2;
    const dp: boolean[] = new Array(targetSum + 1).fill(false);
    dp[0] = true;

    for (const num of nums) {
        for (let i = targetSum; i >= num; i--) {
            dp[i] = dp[i] || dp[i - num];
        }
    }

    return dp[targetSum];
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function canPartition($nums) {
        $total = array_sum($nums);
        if ($total % 2 != 0) {
            return false;
        }
        
        $half = $total / 2;
        $dp = array_fill(0, $half + 1, false);
        $dp[0] = true;
        
        foreach ($nums as $num) {
            for ($i = $half; $i >= $num; $i--) {
                $dp[$i] = $dp[$i] || $dp[$i - $num];
            }
        }
        
        return $dp[$half];
    }
}

                                            
class Solution {
    func canPartition(_ nums: [Int]) -> Bool {
        let totalSum = nums.reduce(0, +)
        if totalSum % 2 != 0 {
            return false
        }
        
        let target = totalSum / 2
        var dp = Array(repeating: false, count: target + 1)
        dp[0] = true
        
        for num in nums {
            var index = target
            while index >= num {
                dp[index] = dp[index] || dp[index - num]
                index -= 1
            }
        }
        
        return dp[target]
    }
}

                                            
class Solution {
    fun canPartition(nums: IntArray): Boolean {
        val totalSum = nums.sum()
        if (totalSum % 2 != 0) return false

        val targetSum = totalSum / 2
        val dp = BooleanArray(targetSum + 1)
        dp[0] = true

        for (num in nums) {
            for (i in targetSum downTo num) {
                dp[i] = dp[i] || dp[i - num]
            }
        }

        return dp[targetSum]
    }
}

                                            
class Solution {
  bool canPartition(List<int> nums) {
    int sum = nums.reduce((value, element) => value + element);
    if (sum % 2 != 0) {
      return false;
    }
    int target = sum ~/ 2;
    List<bool> dp = List.filled(target + 1, false);
    dp[0] = true;

    for (int num in nums) {
      for (int i = target; i >= num; i--) {
        dp[i] = dp[i] || dp[i - num];
      }
    }

    return dp[target];
  }
}

                                            
func canPartition(nums []int) bool {
    total := 0
    for _, num := range nums {
        total += num
    }
    if total%2 != 0 {
        return false
    }
    half := total / 2
    dp := make([]bool, half+1)
    dp[0] = true
    for _, num := range nums {
        for i := half; i >= num; i-- {
            dp[i] = dp[i] || dp[i-num]
        }
    }
    return dp[half]
}

                                            
# @param {Integer[]} nums
# @return {Boolean}
def can_partition(nums)
    total = nums.sum
    return false if total.odd?
    
    target = total / 2
    dp = Array.new(target + 1, false)
    dp[0] = true
    
    nums.each do |num|
        (target - num).downto(0) do |i|
            dp[i + num] = true if dp[i]
        end
    end
    
    dp[target]
end

                                            
object Solution {
    def canPartition(nums: Array[Int]): Boolean = {
        val totalSum = nums.sum
        if (totalSum % 2 != 0) return false
        
        val target = totalSum / 2
        val dp = Array.ofDim[Boolean](nums.length + 1, target + 1)
        
        for (i <- 0 to nums.length) {
            dp(i)(0) = true
        }
        
        for (i <- 1 to nums.length; j <- 1 to target) {
            dp(i)(j) = dp(i - 1)(j) || (j >= nums(i - 1) && dp(i - 1)(j - nums(i - 1)))
        }
        
        dp(nums.length)(target)
    }
}

                                            
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) as usize;
        let mut dp = vec![false; target + 1];
        dp[0] = true;
        
        for num in nums {
            for i in (num as usize..=target).rev() {
                dp[i] = dp[i] || dp[i - num as usize];
            }
        }
        
        dp[target]
    }
}

                                            
-spec can_partition(Nums :: [integer()]) -> boolean
().
can_partition(Nums) ->
    Total = lists:sum(Nums),
    case Total rem 2 of
        1 -> false; % If total sum is odd, can't partition into equal subsets
        _ -> can_partition(Nums, Total div 2)
    end.

can_partition([], 0) -> true;
can_partition(_, 0) -> true;
can_partition([], _) -> false;
can_partition([H|T], Total) -> can_partition(T, Total) orelse can_partition(T, Total-H).

To solve this coding challenge, we need to determine whether a given array of integers can be partitioned into two subsets such that the sum of the elements in both subsets is equal. This problem can be approached using Dynamic Programming (DP).

Explanation

Problem Breakdown:

Understand Input and Output:

You are given an integer array
nums

.
The goal is to check if you can split this array into two subsets with equal sums.

Initial Checks:

First, calculate the sum of all elements in the array.
If the sum is odd, it's impossible to partition the array into two subsets with equal sums (since two equal integers summed must be even). In this case, immediately return
False

.

Define Subset Sum Problem:

Calculate half of the total sum (
half_sum

). If we can find a subset of
nums

that sums up to
half_sum

, then the other subset will naturally also sum to
half_sum

.
This problem is essentially a variation of the "Knapsack" problem, where we determine if a subset with a given sum exists.

Dynamic Programming Approach:

DP Table Initialization:

Create a boolean DP array
dp

where
dp[i]

means whether a subset sum
i

can be achieved using the elements from the array.
Initialize
dp[0]

to
True

because a subset sum of 0 can always be achieved with an empty subset.

Filling the DP Table:

Iterate through the numbers in the array.
For each number
num

, update the DP table from right to left (i.e., from
half_sum

to
num

). This avoids overcounting the current element.
For each
i

from
half_sum

down to
num

, set
dp[i]

to
True

if
dp[i - num]

is
True

. This simulates including the current number in the subset.

Final Check:

The answer to the problem will be
dp[half_sum]

. If it's
True

, it means there exists a subset in
nums

that sums up to
half_sum

.

Pseudocode with Comments

                                            
# Function to determine if we can partition the array into two subsets with equal sum
function canPartition(nums)
# Calculate the total sum of the elements in the array
total_sum = sum(nums)

# If the total sum is odd, we cannot partition it into two subsets with equal sum
if total_sum % 2 != 0:
return False

# Calculate the target sum for one subset
half_sum = total_sum // 2

# Initialize a DP array where dp[i] indicates if a subset sum of i can be achieved
dp = array of size (half_sum + 1) with all values False
dp[0] = True  # A subset sum of 0 can always be achieved with an empty set

# Iterate through each number in the array
for each num in nums:
# Update the DP table from right to left
for i from half_sum downto num:
dp[i] = dp[i] or dp[i - num]

# The answer will be whether half_sum can be formed as a subset sum
return dp[half_sum]

Detailed Steps in Pseudocode

Initialize Variables:

Calculate
total_sum

as the sum of all elements in
nums

.
Check the parity of
total_sum

. If it's odd, return
False

as partitioning into two equal subsets is impossible.

Calculate Target Subset Sum:

Compute
half_sum

as half of
total_sum

.

Initialize DP Array:

Create a boolean array
dp

of size
half_sum + 1

, initially set to
False

.
Set
dp[0]

to
True

.

Update DP Array:

Loop through each number
num

in
nums

.
For each number, update the DP array from right (from
half_sum

to
num

) to left:

Set
dp[i]

to
True

if
dp[i - num]

is
True

.

Return Result:

Finally, return the value of
dp[half_sum]

, which indicates if a subset with a sum of
half_sum

exists.

By following these steps meticulously, we can determine if the given array can be partitioned into two subsets of equal sum or not. This approach ensures an optimal and efficient solution with O(n * half_sum) time complexity and O(half_sum) space complexity.