給定一個(gè)只包含正整數(shù)的非空數(shù)組锈麸。是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等撞羽。

class Solution {
    public boolean canPartition(int[] nums) {
        if(nums.length == 0) return false;
        int sum = 0;
        for(int i:nums){
            sum += i;
        }
        if(sum % 2 == 1)return false;//集合總和為奇數(shù)
        boolean[] dp = new boolean[sum+1];
        dp[0] = true;   
        for (int j = 0; j < nums.length; j++) {
                for (int k = sum; k >= 0 && k >= nums[j]; k--) {
                        dp[k] =  dp[k] || dp[k-nums[j]];
                }
                if(dp[sum / 2]) {//存在某個(gè)子集的和sum / 2
                    return true;
                }
            }
        return false;
    }
}

京東2018校招求神奇數(shù)
東東在一本古籍上看到有一種神奇數(shù)认罩，如果能夠?qū)⒁粋€(gè)數(shù)的數(shù)字分成兩組，其中一組數(shù)字的和等于另一組數(shù)字的和掰担，我們就將這個(gè)數(shù)稱為神奇數(shù)汇陆。例如242就是一個(gè)神奇數(shù)，我們能夠?qū)⑦@個(gè)數(shù)的數(shù)字分成兩組,分別是{2,2}以及{4},而且這兩組數(shù)的和都是4带饱。東東現(xiàn)在需要統(tǒng)計(jì)給定區(qū)間中有多少個(gè)神奇數(shù)毡代，即給定區(qū)間[l, r]，統(tǒng)計(jì)這個(gè)區(qū)間中有多少個(gè)神奇數(shù)勺疼，請(qǐng)你來幫助他

public class jd {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        int start = sc.nextInt();
        int end =sc.nextInt();
        System.out.println(findMagicNumber(start, end));
        sc.close();
        
    }
    static public int findMagicNumber(int start, int end) {
        int ans = 0;
        int[] digitals = new int[10];
        boolean[] dp = new boolean[9 * 9];
        Arrays.fill(digitals, -1);
        Arrays.fill(dp, false);
        dp[0] = true;
        for (int i = start; i <= end; i++) {
            int num = i;
            int sum = 0;
            int index = 0;
            while (num > 0) {
                int temp = num % 10;
                digitals[index++] = temp;
                sum += temp;
                num = num / 10;
            }
            // 當(dāng)各位數(shù)字和為偶數(shù)時(shí)教寂，才存在神奇數(shù)
            if ((sum & 1) == 0){
                for (int j = 0; j < digitals.length && digitals[j] != -1; j++) {
                    for (int k = sum; k >= 0; k--) {
                        // 用一維數(shù)組進(jìn)行更新
                        if(k >= digitals[j]) {
                            dp[k] = dp[k] || dp[k-digitals[j]];
                            System.out.println(k+" "+digitals[j]+" "+dp[k]);
                        }
                            
                    }
                    if(dp[sum / 2]) {
                        ans++;
                        System.out.println(i);
                        break;
                    }
                }
            }
            Arrays.fill(digitals, -1);
            Arrays.fill(dp, false);
            dp[0] = true;
        }
        return ans;
    }
}