5. MELON的难题

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const lines = [];
rl.on('line', (line) => {
    lines.push(line);
});
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const stones = lines[1].split(' ').map(Number);
    let totalWeight = 0;
    for(let v of stones) {
        totalWeight += v;
    }
    if (totalWeight % 2 !== 0) {
        console.log(-1);
    } else {
        const target = totalWeight / 2;
        const dp = new Array(target+1).fill(0);
        for(let i=1; i<=target; i++) {
            dp[i] = n;
        }

        for(let i=1; i<=n; i++) {
            const weight = stones[i-1];
            for(let j=target; j>=weight; j--) {
                dp[j] = Math.min(dp[j], dp[j-weight] + 1);
            }
        }

        if (dp[target] === n) {
            console.log(-1);
        } else {
            console.log(dp[target]);
        }
    }
})