ตรวจสอบว่ากลับสู่ 12 โมงได้โดยบวก/ลบวินาทีที่กำหนดหรือไม่ด้วย Python

มี Array วินาที ต้องเช็คว่าเริ่ม 12 โมง บวก/ลบวินาทีแต่ละค่า ครบ 1 รอบ (24*60 นาที) กลับมา 12 โมงได้หรือไม่ (ใช้ทุกค่า 1 ครั้ง)

เช่น Input seconds = [40,90,50] Output True (+40 -90 +50 = 0)

ขั้นตอนแก้ (Brute Force Subset Sum):

• Size = 2^n (n = จำนวนวินาที)
• ลองทุก Combination ของ +/- โดย Bitmask
• ถ้า Sum หาร 1440 (24*60) ลงตัว Return True

ตัวอย่างโค้ด

def solve(seconds):
    size = 2**len(seconds)
    for c in range(size):
        add = 0
        for j in range(len(seconds)):
            if c & (1 << j):
                add += seconds[j]
            else:
                add -= seconds[j]
        if add % (24 * 60) == 0:
            return True
    return False

seconds = [40,90,50]
print(solve(seconds))

Input

[40,90,50]

Output

True