package code;

import java.util.HashSet;
/*
 * 416. Partition Equal Subset Sum
 * 
 * Medium
 * Dynamic Programming
 * /2 lc1, lc15 3-Sum 
 *      dfs2^n
 *      01
 *      0101
 *       dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
 *       ijj
 * Tipslc416, lc494
 */
public class lc416 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 5};
        System.out.println(canPartition(nums));
    }
    public static boolean canPartition(int[] nums) {    //
        int sum = 0;
        for (int i : nums) {
            sum+=i;
        }
        if(sum%2==1)
            return false;
        sum/=2;
        HashSet s = new HashSet();
        for (int i = 0; i < nums.length ; i++) {
            if(nums[i]==sum)
                return true;
            HashSet s2 = new HashSet();    // set,
            s2.add(nums[i]);
            for(int j: s){
                if(j+nums[i]==sum)
                    return true;
                s2.add(j+nums[i]);
            }
            s.addAll(s2);
        }
        return false;
    }

    public boolean canPartition2(int[] nums) {
        // check edge case
        if (nums == null || nums.length == 0) {
            return true;
        }
        // preprocess
        int volumn = 0;
        for (int num : nums) {
            volumn += num;
        }
        if (volumn % 2 != 0) {
            return false;
        }
        volumn /= 2;
        // dp def
        boolean[] dp = new boolean[volumn + 1];
        // dp init
        dp[0] = true;
        // dp transition
        for (int i = 1; i = nums[i-1]; j--) { //
                dp[j] = dp[j] || dp[j - nums[i-1]];
            }
        }
        return dp[volumn];
    }

    public boolean canPartition3(int[] nums) {
        int sum = 0;
        for(int i: nums) sum+=i;
        if(sum%2==1) return false;
        sum = sum/2;
        boolean[][] dp = new boolean[nums.length+1][sum+1];
        for(int i =0; i