正数数组的最小不可组成和

正数数组的最小不可组成和

正整数数组的最小不可组成和

【题目】
给定一个正整数数组arr，arr中至少一个元素累加可得到不同的累加值（可组成和），
将可组成和按升序排列，从最小值计算，筛选出最小的不可组成和。

举例：
arr=[3, 2, 5]，可组成和升序排列为{2, 3, 5, 7, 8, 10}，最小不可组成和为4；
arr=[1, 2, 4]，可组成和升序排列为{1, 2, 3, 4, 5, 6, 7}，最小不可组成和为8；

暴力递归

求出每一个非空子集的累加和。
非空子集个数为$O(2^N) - 1$O(2N)−1，所求累加和存储在哈希集合中。
因此时间复杂度为$O(2^N)$O(2N)，最坏空间复杂度为$O(2^N)$O(2N)（累加和都不相同 e.g. arr=[1, 2, 4]）。

相应代码

def unformedSum1(arr):
    if arr == None or len(arr) == 0:
        return 1
    sub_sums = set()
    process(arr, 0, len(arr), 0, sub_sums)
    sub_sums.remove(0)  # 至少包含一个值
    minimum = arr[0]
    for i in range(1, len(arr)):
        if arr[i] < minimum:
            minimum = arr[i]
    for i in range(minimum, minimum + len(sub_sums) + 2):
        if i not in sub_sums:
            return i

def process(arr, i, j, sub_sum, sub_sums):
    if i == j:
        if sub_sum not in sub_sums:
            sub_sums.add(sub_sum)
        return
    process(arr, i + 1, j, sub_sum + arr[i], sub_sums)  # 组成和包括arr[i]
    process(arr, i + 1, j, sub_sum, sub_sums)  # 组成和不包括arr[i]

# 简单测试
if __name__ == '__main__':
    arr = [3, 2, 5]
    print(unformedSum1(arr))  # 最小不可组成和为4
    arr = [1, 2, 4]
    print(unformedSum1(arr))  # 最小不可组成和为8

动态规划

arr[0…i]非空累加出k，那么 arr[0…i+1]则必然可以非空累加出k+arr[i+1]。（递推公式）
创建布尔数组dp，dp[j]为True表示arr[0…i]可以非空累加到j；
arr为正整数数组，因此累加和最大值MAX_SUM为所有元素之和；
因此arr[0…i]的累加范围必定在[0, MAX_SUM]中；
时间复杂度为O($N * MAX\_SUM$N∗MAX_SUM)，额外空间复杂度为O($MAX\_SUM$MAX_SUM)，最坏空间复杂度为O($2^N$2N)。

相应代码

def unformedSum2(arr):
    if arr is None or len(arr) == 0:
        return 1
    max_sum = arr[0]  # 最大的可组成和
    min_sum = arr[0]  # 最小的可组成和
    for i in range(1, len(arr)):
        max_sum += arr[i]
        if arr[i] < min_sum:
            min_sum = arr[i]
    dp = [False for i in range(max_sum + 1)]
    dp[0] = True
    for i in range(0, len(arr)):
        # 必须从最大值降序判断，否则会造成重复累加
        for j in range(max_sum, min_sum - 1, -1):
            if j - arr[i] >= 0 and dp[j - arr[i]] is True:
                dp[j] = True
    # 最小的不可组成和
    for i in range(min_sum, len(dp)):
        if dp[i] is False:
            return i
    return max_sum + 1

# 简单测试
if __name__ == '__main__':
    arr = [3, 2, 5]
    print(unformedSum2(arr))  # 最小不可组成和为4
    arr = [1, 2, 4]
    print(unformedSum2(arr))  # 最小不可组成和为8

包含1的正整数数组的最小不可组成和

【进阶问题】
如果正整数数组arr必定包含1，求其最小不可组成和。

算法思路

在正整数数组中最小可组成和必定为1，也就是从1开始找最小不可组成和。
将数组升序排序，可组成和范围scale则从0开始扩大。
若scale + 1 >= arr[i]则扩大范围
否则找到正数数组最小不可组成和——scale + 1。

时间复杂度为$O(NlogN)$O(NlogN)，额外空间复杂度为$O(1)$O(1)。

相应代码

# 进阶问题:如果正整数数组arr必定包含1
def unformedSum3(arr):
    # 升序排序
    arr = sorted(arr)
    scale = 0
    for i in range(len(arr)):
        # 扩大范围
        if scale + 1 >= arr[i]:
            scale += arr[i]
        else:
            break
    return scale + 1

# 简单测试
if __name__ == '__main__':
    # 进阶问题:如果正整数数组arr必定包含1
    arr = [3, 8, 1, 2]
    print(unformedSum3(arr))  # 最小不可组成和为7
    arr = [3, 8, 1, 2, 4]
    print(unformedSum3(arr))  # 最小不可组成和为19

思考

思维扩展
那么整数数组有没有最小不可组成和呢？（正整数——>整数）
  倘若可以拓展最小不可组成和的概念：从最小值起逐一增大的最小不可组成和，解法依然相同（同暴力递归，动态规划）。但是数组异常情况（arr is None or len(arr) == 0）应该返回None或者报异常。
  有人觉得最小可组成和为-3，那么-4应该是最小可组成和，其实不然，$-\infty$−∞也无法组成，且$-\infty$−∞比任何数都少，因此按照这种想法不存在最小不可组成和

那么正数数组有没有最小不可组成和呢？（整数——>浮点数）
  正数数组没有最小不可组成和，因为浮点数可以无限循环(e.g 比1大的第一个数无法找出)。

有任何疑问和建议，欢迎在评论区留言和指正！

感谢您所花费的时间与精力！