Tìm số nguyên dương nhỏ nhất không thể biểu diễn thành tổng tập con trong Python

Cho mảng đã sắp xếp tăng dần các số nguyên dương. Ta cần tìm số nguyên dương nhỏ nhất không thể biểu diễn thành tổng của bất kỳ tập con nào của mảng. Độ phức tạp O(n).

Ví dụ, với A = [1, 4, 8, 12, 13, 17], kết quả là 2.

Thuật toán giải quyết

• answer := 1.
• Duyệt qua mảng:
  • Nếu A[i] <= answer: answer += A[i].
  • Ngược lại: thoát vòng lặp.
• Trả về answer.

Ví dụ minh họa

def get_smallest_element(A):
    n = len(A)
    answer = 1
    for i in range(n):
        if A[i] <= answer:
            answer += A[i]
        else:
            break
    return answer

A = [1, 4, 8, 12, 13, 17]
print(get_smallest_element(A))  # 2

Đầu vào

[1, 4, 8, 12, 13, 17]

Đầu ra

2