---

前言

给定一个正数数组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;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

题目二题解

先把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;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16