给定一个正数数组arr，返回arr的子集不能累加出的最小正数。1）正常怎么做？ 2）如果arr中肯定有1这个值，怎么做？
先排序，然后扩充range范围。
1.b<=range+1,扩充到range+b。
2.b>range+1,直接返回range+1。
时间复杂度：排序的。
空间复杂度：排序的。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
"sort"
)
func main() {
arr := []int{1, 2, 5}
if true {
ret := unformedSum1(arr)
fmt.Println(ret)
}
if true {
ret := unformedSum2(arr)
fmt.Println(ret)
}
if true {
ret := unformedSum3(arr)
fmt.Println(ret)
}
}
func unformedSum1(arr []int) int {
if len(arr) == 0 {
return 1
}
set := make(map[int]struct{})
process(arr, 0, 0, set)
min := math.MaxInt64
for i := 0; i != len(arr); i++ {
min = getMin(min, arr[i])
}
for i := min + 1; i != math.MinInt64; i++ {
if _, ok := set[i]; !ok {
return i
}
}
return 0
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
func process(arr []int, i int, sum int, set map[int]struct{}) {
if i == len(arr) {
set[sum] = struct{}{}
return
}
process(arr, i+1, sum, set)
process(arr, i+1, sum+arr[i], set)
}
func unformedSum2(arr []int) int {
if len(arr) == 0 {
return 1
}
sum := 0
min := math.MaxInt64
for i := 0; i != len(arr); i++ {
sum += arr[i]
min = getMin(min, arr[i])
}
// boolean[][] dp ...
N := len(arr)
dp := make([][]bool, N)
for i := 0; i < N; i++ {
dp[i] = make([]bool, sum+1)
}
for i := 0; i < N; i++ { // arr[0..i] 0
dp[i][0] = true
}
dp[0][arr[0]] = true
for i := 1; i < N; i++ {
for j := 1; j <= sum; j++ {
if j-arr[i] >= 0 {
dp[i][j] = dp[i-1][j] || (dp[i-1][j-arr[i]])
} else {
dp[i][j] = dp[i-1][j] || (false)
}
}
}
for j := min; j <= sum; j++ {
if !dp[N-1][j] {
return j
}
}
return sum + 1
}
// 已知arr中肯定有1这个数
func unformedSum3(arr []int) int {
if len(arr) == 0 {
return 0
}
sort.Slice(arr, func(i, j int) bool {
return arr[i] < arr[j] // O (N * logN)
})
range2 := 1
// arr[0] == 1
for i := 1; i != len(arr); i++ {
if arr[i] > range2+1 {
return range2 + 1
} else {
range2 += arr[i]
}
}
return range2 + 1
}执行结果如下：
