@TOC

前言

给定一个正数数组arr，
返回arr的子集不能累加出的最小正数
1）正常怎么做？
2）如果arr中肯定有1这个值，怎么做？

问题一解决思路

arr所有值的累加和从一个负数到一个整数做出一张表,然后看最后一行
arr 0~N-1最后一行的值能不能搞定1, 2, 3...哪一个最早不行的,返回就是答案

    public static int unformedSum2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 1;
        }
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i != arr.length; i++) {
            sum += arr[i];
            min = Math.min(min, arr[i]);
        }
        // boolean[][] dp ...
        int N = arr.length;
        boolean[][] dp = new boolean[N][sum + 1];
        for (int i = 0; i < N; i++) {// arr[0..i] 0
            dp[i][0] = true;
        }
        dp[0][arr[0]] = true;
        for (int i = 1; i < N; i++) {
            for (int j = 1; j <= sum; j++) {
                dp[i][j] = dp[i - 1][j] || ((j - arr[i] >= 0) ? dp[i - 1][j - arr[i]] : false);
            }
        }
        for (int j = min; j <= sum; j++) {
            if (!dp[N - 1][j]) {
                return j;
            }
        }
        return sum + 1;
    }

题目二题解

先把array排序,正数数组排完序，左边0位置肯定是1
定义变量range =1,表示从1~ 1范围上的正数都能累加出来
range=k,代表1~k上的所有正数都能搞出来

当arr 0位置是1的情况下，range=1,代表1~ 1范围的正数都可以搞出来
如果1位置也是1, range变成2,代表1 ~2范围的正数都可以搞出来

如果2位置也是2, range变成4,代表1 ~4范围的正数都可以搞出来

如果0~ i-1是0~100, range=100
i位置17,可以让range扩充到117

如果0~ i-1能搞定的数是1~100,此时i位置是102,那么101不可以搞定

如果0~ i搞定1~a,如果位置上是b:
1如果b<=a+1,能扩充范围到1~a+b
2咖如果b> a+1. a+1就是搞定不了的最小正整数

    public static int unformedSum3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        Arrays.sort(arr); // O (N * logN)
        int range = 1;
        // arr[0] == 1
        for (int i = 1; i != arr.length; i++) {
            if (arr[i] > range + 1) {
                return range + 1;
            } else {
                range += arr[i];
            }
        }
        return range + 1;
    }