Chương trình Python rút gọn danh sách bằng phép trừ tìm số nhỏ nhất còn lại

Cho danh sách số dương nums. Phép toán: chọn a ≤ b, nếu a < b thì xóa cả hai và thêm b-a vào danh sách. Lặp lại tùy ý. Tìm số nhỏ nhất có thể còn lại (0 nếu rỗng).

Ví dụ

Input: nums = [2, 4, 5]

Output: 1

Giải thích: Chọn 4,5 → thêm 1 → [2,1]. Chọn 2,1 → thêm 1 → [1].

Thuật toán (Quy hoạch động / Subset Sum)

Bài toán tương đương: chia tập hợp thành 2 nhóm sao cho hiệu 2 tổng nhỏ nhất (tức là tổng 2 nhóm gần nhau nhất).

• Tổng S = sum(nums).
• Tìm tập con có tổng gần S/2 nhất → hiệu nhỏ nhất = |S - 2*subset_sum|.
• Đệ quy thử chọn/bỏ mỗi phần tử.

Mã nguồn Python

def solve(nums):
    S = sum(nums)

    def f(i, s):
        if i >= len(nums):
            return s
        n = nums[i]
        if s - 2 * n < 0:
            return f(i + 1, s)
        return min(f(i + 1, s - 2 * n), f(i + 1, s))

    return f(0, S)

# Test
nums = [2, 4, 5]
print(solve(nums))  # Output: 1

Độ phức tạp

• Thời gian: O(2ⁿ) (đệ quy nhánh). Có thể tối ưu bằng DP bottom-up O(n*S).
• Không gian: O(n) stack đệ quy.

Lưu ý: Đây là bài toán Partition Problem (NP-hard), giải pháp đệ quy chỉ phù hợp n nhỏ. Với n lớn, dùng DP bitset hoặc mảng boolean.