Equal Payload Partition — Problem Statement & Solution Guide

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int64 dfs(int idx, int cur, int target, const vector<int>& w, vector<unordered_map<int,int64>>& memo){
    if(idx==(int)w.size()) return cur==target ? 1 : 0;
    auto it=memo[idx].find(cur);
    if(it!=memo[idx].end()) return it->second;
    int64 ways=0;
    // take element
    ways+=dfs(idx+1, cur+w[idx], target, w, memo);
    // skip element
    ways+=dfs(idx+1, cur, target, w, memo);
    memo[idx][cur]=ways;
    return ways;
}

int countPartitions(const vector<int>& weights){
    long long total=0; for(int v:weights) total+=v;
    if(total%2!=0) return 0;
    int target=total/2;
    vector<unordered_map<int,int64>> memo(weights.size());
    return (int)dfs(0,0,target,weights,memo);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<int> w(n);
    for(int i=0;i<n;++i) cin>>w[i];
    cout<<countPartitions(w);
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    private static long dfs(int idx, int cur, int target, int[] w, Map<Long,Long> memo){
        if(idx==w.length) return cur==target ? 1L : 0L;
        long key = ((long)idx<<32) | (cur & 0xffffffffL);
        Long cached = memo.get(key);
        if(cached!=null) return cached;
        long ways = dfs(idx+1, cur + w[idx], target, w, memo) + dfs(idx+1, cur, target, w, memo);
        memo.put(key, ways);
        return ways;
    }
    public static long countPartitions(int[] weights){
        long total=0; for(int v:weights) total+=v;
        if((total & 1L)==1L) return 0L;
        int target = (int)(total/2);
        Map<Long,Long> memo = new HashMap<>();
        return dfs(0,0,target,weights,memo);
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        if(line==null||line.isEmpty()) return;
        int n = Integer.parseInt(line.trim());
        int[] w = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) w[i]=Integer.parseInt(st.nextToken());
        System.out.println(countPartitions(w));
    }
}

import sys
from functools import lru_cache

def count_partitions(weights):
    total = sum(weights)
    if total % 2:
        return 0
    target = total // 2
    @lru_cache(maxsize=None)
    def dfs(idx, cur):
        if idx == len(weights):
            return 1 if cur == target else 0
        # include
        take = dfs(idx+1, cur + weights[idx])
        # exclude
        skip = dfs(idx+1, cur)
        return take + skip
    return dfs(0, 0)

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    weights = list(map(int, data[1:1+n]))
    print(count_partitions(weights))

if __name__ == "__main__":
    main()

const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0){process.exit(0);} 
let pos=0;
const n=data[pos++];
const weights=data.slice(pos, pos+n);

function countPartitions(arr){
    const total = arr.reduce((a,b)=>a+b,0);
    if(total%2!==0) return 0;
    const target = total/2;
    const memo = new Map(); // key: idx|sum
    function dfs(idx,sum){
        if(idx===arr.length) return sum===target ? 1 : 0;
        const key = idx+','+sum;
        if(memo.has(key)) return memo.get(key);
        let ways = dfs(idx+1,sum+arr[idx]) + dfs(idx+1,sum);
        memo.set(key,ways);
        return ways;
    }
    return dfs(0,0);
}

console.log(countPartitions(weights).toString());