public class Solution {
    // public boolean canPartition(int[] nums) {
    //     int s = 0;
    //     for(int n:nums){
    //         s += n;
    //     }
    //     if(s%2!=0) return false;
    //     s = s/2;
    //     boolean[] d = new boolean[s+1];
    //     d[0] = true;
    //     for(int i=0;i<nums.length;i++){
    //         for(int j=s;j>=0;j--){
    //             if(((j-nums[i])>=0)&&d[j-nums[i]]){
    //                 d[j] = true;
    //             }
    //         }
    //     }
    //     return d[s];
    // }
public boolean canPartition(int[] nums) {
        int sum=0;
        for(int n : nums)
            sum += n;

        if(sum%2==1)
            return false;

        return helper(nums, 0, 0, sum/2, new HashSet<Integer>());
    }

    private boolean helper(int[] nums, int index, int cur, int target, Set<Integer> set){
        if(set.contains(cur))
            return false;
        if(cur==target)
            return true;
        if(cur>target)
            return false;

        for(int i=index; i<nums.length; i++)
            if( helper(nums, i+1, cur+nums[i], target, set) )
                return true;

        set.add(cur);
        return false;
    }



}