class Solution {
    public boolean canPartition(int[] nums) {
        
        int half = 0;
        for (int n: nums) {
            half += n;
        }
        if (half % 2 != 0) return false;

        half = half >> 1;

        boolean[] reach = new boolean[half + 1];
        List<Integer> tmp = new ArrayList<>();

        for (int num: nums) {
            for (int i=1; i<=half; i++) {
                if (reach[i] && i + num <= half) {
                    if (i + num == half) return true;
                    tmp.add(i+num);
                }
            }
            if (num < half) reach[num] = true;
            else if (num == half) return true;
            else return false;

            for (Integer in: tmp) {
                reach[in] = true;
            }
            tmp.clear();
        }

        return false;
    }
}