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

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

福大大 答案2021-08-10：

先排序，然后扩充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

}

执行结果如下：

左神java代码

2021-08-10：给定一个正数数组arr，返回arr的子集不能累加出的最小正数。1）正常怎么做？ 2）如果arr中肯定有1这个值，怎么做？的相关教程结束。