416. Equal partition sum

#include <stdbool.h>
#include <stdlib.h>

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

  bool *dp = calloc(target + 1, sizeof(bool));
  dp[0] = true;

  for (int i = 0; i < numsSize; i++) {
    int x = nums[i];
    // Go backward so each number is used at most once
    for (int s = target; s >= x; s--) {
      if (dp[s - x])
        dp[s] = true;
    }
  }
  bool res = dp[target];
  free(dp);
  return res;
}

#include <numeric>
#include <vector>

using namespace std;

class Solution {
public:
  bool canPartition(vector<int> &nums) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (total % 2 != 0)
      return false;
    int target = total / 2;

    vector<bool> dp(target + 1, false);
    dp[0] = true;

    for (int x : nums) {
      // Go backward so each number is used at most once
      for (int s = target; s >= x; s--) {
        if (dp[s - x])
          dp[s] = true;
      }
    }
    return dp[target];
  }
};

package dp

func canPartition(nums []int) bool {
    total := 0
    for _, x := range nums {
        total += x
    }
    if total%2 != 0 {
        return false
    }
    target := total / 2

    dp := make([]bool, target+1)
    dp[0] = true

    for _, x := range nums {
        // Go backward so each number is used at most once
        for s := target; s >= x; s-- {
            if dp[s-x] {
                dp[s] = true
            }
        }
    }
    return dp[target]
}

import java.util.Arrays;

class Solution {
    public boolean canPartition(int[] nums) {
        int total = Arrays.stream(nums).sum();
        if (total % 2 != 0)
            return false;
        int target = total / 2;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int x : nums) {
            // Go backward so each number is used at most once
            for (int s = target; s >= x; s--) {
                if (dp[s - x])
                    dp[s] = true;
            }
        }
        return dp[target];
    }
}

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  const target = total / 2;

  const dp = new Array(target + 1).fill(false);
  dp[0] = true;

  for (const x of nums) {
    // Go backward so each number is used at most once
    for (let s = target; s >= x; s--) {
      if (dp[s - x]) dp[s] = true;
    }
  }
  return dp[target];
};

from typing import List


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2

        dp = [False] * (target + 1)
        dp[0] = True

        for x in nums:
            # Go backward so each number is used at most once
            for s in range(target, x - 1, -1):
                if dp[s - x]:
                    dp[s] = True
        return dp[target]

impl Solution {
    pub fn can_partition(nums: Vec<i32>) -> bool {
        let total: i32 = nums.iter().sum();
        if total % 2 != 0 {
            return false;
        }
        let target = (total / 2) as usize;

        let mut dp = vec![false; target + 1];
        dp[0] = true;

        for &x in &nums {
            let x = x as usize;
            // Go backward so each number is used at most once
            for s in (x..=target).rev() {
                if dp[s - x] {
                    dp[s] = true;
                }
            }
        }
        dp[target]
    }
}