/**
 * Brute Force - DFS
 * Time O(N^2) | Space O(N)
 * https://leetcode.com/problems/partition-equal-subset-sum/
 * @param {number[]} nums
 * @return {boolean}
 */
 var canPartition = (nums) => {
    const sum = getSum(nums);/* Time O(N) */
    const subSetSum = (sum / 2);

    const isEven = ((sum % 2) === 0);
    if (!isEven) return false;

    const index = (nums.length - 1);

    return dfs(nums, index, subSetSum);
}

var getSum = (nums, sum = 0) => {
    for (const num of nums) (sum += num);/* Time O(N) */

    return sum;
}

var dfs = (nums, index, subSetSum) => {
    const isBaseCase1 = subSetSum === 0;
    if (isBaseCase1) return true;

    const isBaseCase2 = (index === 0) || (subSetSum < 0);
    if (isBaseCase2) return false;

    const difference = (subSetSum - nums[(index - 1)]);

    const left = dfs(nums, (index - 1), difference);
    const right = dfs(nums, (index - 1), subSetSum);

    return (left || right);
}

/**
 * DP - Top Down
 * Matrix - Memo
 * Time O(N * M) | Space O(N * M)
 * https://leetcode.com/problems/partition-equal-subset-sum/
 * @param {number[]} nums
 * @return {boolean}
 */
 var canPartition = (nums) => {
    const isEmpty = nums.length === 0;
    if (isEmpty) return false;

    const sum = getSum(nums);                 /* Time O(N) */

    const isEven = ((sum % 2) === 0);
    if (!isEven) return false;

    const subSetSum = (sum >> 1);
    const memo = initMemo(nums, subSetSum);        /*               | Space O(N * M) */
    const index = (nums.length - 1);

    return dfs(nums, index, subSetSum, memo);/* Time O(N * M) | Space O(N * M) */
}

var initMemo = (nums, subSetSum) => new Array((nums.length + 1)).fill()/* Space O(N) */
    .map(() => new Array((subSetSum + 1)).fill(null));                     /* Space O(M) */

var dfs = (nums, index, subSetSum, memo) => {
    const isBaseCase1 = (subSetSum === 0);
    if (isBaseCase1) return true;

    const isBaseCase2 = ((index === 0) || (subSetSum < 0));
    if (isBaseCase2) return false;

    const hasSeen = (memo[index][subSetSum] !== null);
    if (hasSeen) return memo[index][subSetSum];

    const difference = (subSetSum - nums[(index - 1)]);

    const left = dfs(nums, (index - 1), difference, memo);
    const right = dfs(nums, (index - 1), subSetSum, memo);

    memo[index][subSetSum] = (left || right);
    return memo[index][subSetSum];
}

/**
 * DP - Bottom Up
 * Matrix - Tabulation
 * Time O(N * M) | Space O(N * M)
 * https://leetcode.com/problems/partition-equal-subset-sum/
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = (nums) => {
    const isEmpty = nums.length === 0;
    if (isEmpty) return false;

    const sum = getSum(nums);              /* Time O(N) */

    const isEven = ((sum % 2) === 0);
    if (!isEven) return false;

    const subSetSum = (sum >> 1);
    const tabu = initTabu(nums, subSetSum);/*            | Space O(N * M) */

    search(nums, subSetSum, tabu);

    return tabu[nums.length][subSetSum];
}

var getSum = (nums, sum = 0) => {
    for (const num of nums) { sum += num };/* Time O(N) */

    return sum;
}

var initTabu = (nums, subSetSum) => {
    const tabu = new Array((nums.length + 1)).fill()/* Space O(N) */
        .map(() => new Array((subSetSum + 1)).fill(false));/* Space O(M) */

    tabu[0][0] = true;                              /* Space O(N * M) */

    return tabu;
}

var search = (nums, subSetSum, tabu) => {
    for (let numIndex = 1; (numIndex <= nums.length); numIndex++) {/* Time O(N) */
        update(nums, numIndex, subSetSum, tabu);                       /* Time O(N) | Space O(N * M) */
    }
}

var update = (nums, numIndex, subSetSum, tabu) => {
    const num = (numIndex - 1);
    const prevNum = nums[num];

    for (let subSet = 0; subSet <= subSetSum; subSet++) {/* Time O(M) */
        const isNumGreater = (subSet < prevNum);

        tabu[numIndex][subSet] = isNumGreater               /* Space O(N * M) */
            ? (tabu[num][subSet])
            : ((tabu[num][subSet]) || (tabu[num][subSet - prevNum]));
    }
}

/**
 * DP - Bottom Up
 * Array - Tabulation
 * Time O(N * M) | Space O(M)
 * https://leetcode.com/problems/partition-equal-subset-sum/
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = (nums) => {
    const isEmpty = nums.length === 0;
    if (isEmpty) return false;

    const sum = getSum(nums);        /* Time O(N) */

    const isEven = ((sum % 2) === 0);
    if (!isEven) return false;

    const subSetSum = (sum >> 1);
    const tabu = initTabu(subSetSum);/*               | Space O(M) */

    search(nums, subSetSum, tabu);   /* Time O(N * M) | Space O(M) */

    return tabu[subSetSum];
};

var getSum = (nums, sum = 0) => {
    for (const num of nums) { sum += num };/* Time O(N) */

    return sum;
}

var initTabu = (subSetSum) => {
    const tabu = new Array((subSetSum + 1)).fill(false);/* Space O(M) */

    tabu[0] = true;                                     /* Space O(M) */

    return tabu;
}

var search = (nums, subSetSum, tabu) => {
    for (const num of nums) {/* Time O(N) */
        update(num, subSetSum, tabu);/* Time O(M) | Space O(M) */
    }
}

var update = (num, subSetSum, tabu) => {
    for (let subSet = subSetSum; (num <= subSet); subSet--) {/* Time O(M) */
        const difference = (subSet - num);

        tabu[subSet] |= tabu[difference];                        /* Space O(M) */
    }
}