ข้อ 58 · LC216 Combination Sum III (ผลรวมชุดค่า III) 🟡

โจทย์ (LC216): กำหนดจำนวนเต็ม k กับ n มา ให้หาทุก combination ที่ใช้ได้ของเลขจำนวนเต็ม k ตัว ซึ่ง sum แล้วได้เท่ากับ n โดยมีเงื่อนไขว่าใช้ได้เฉพาะเลข 1 ถึง 9 เท่านั้น และแต่ละเลขใช้ได้อย่างมากหนึ่งครั้ง ให้ return list ของทุก combination ที่ใช้ได้ (ห้ามมี combination ซ้ำกัน ลำดับใน list ไม่สำคัญ)

แนวทาง — ต้องใช้อะไร & คิดยังไง

ยังเป็น backtracking แต่โจทย์นี้เพิ่มเงื่อนไขสองอย่างที่ต้องคุมพร้อมกัน: count (จำนวน) ตัวต้องเป็น k พอดี และ sum ต้องเป็น n พอดี เราจึงพก remaining (ค่าที่เหลือต้องเติมให้ครบ n) และ compare (เทียบ) length ของ path กับ k

ประเด็นสำคัญคือกัน combination ซ้ำ เช่น [1,2,4] กับ [4,2,1] ต้องนับเป็นชุดเดียว วิธีที่สะอาดที่สุดคือบังคับให้ choose จากน้อยไปมากเสมอ โดยส่งค่า start บอกว่าเลขถัดไปต้องเริ่มจากตัวไหน ทำให้แต่ละ combination ออกมา sorted (เรียง) อยู่แล้ว จึงไม่มีทางได้ชุดที่เป็นการ permute (สลับลำดับ) ของกันและกัน

นอกจากนี้ยังทำ pruning (ตัดกิ่ง) ได้: ถ้าเลขที่กำลังจะ choose มากกว่า remaining แล้ว ตัวถัด ๆ ไปยิ่งใหญ่กว่า จึงหยุด loop ทันทีด้วย break ไม่ต้องเสียเวลา iterate ต่อ

1. initialize result และ path เขียนฟังก์ชัน backtrack(start, remaining)
2. ถ้า len(path) == k แปลว่า choose ครบจำนวนแล้ว: ถ้า remaining == 0 พอดี ให้เก็บ copy (สำเนา) ของ path ลง result แล้ว return ไม่ว่ากรณีใด
3. iterate num จาก start ถึง 9: ถ้า num > remaining ให้ break (pruning)
4. ไม่งั้น choose (append num) → explore (backtrack(num+1, remaining-num)) → unchoose (pop)
5. เริ่มด้วย backtrack(1, n)

ไล่ทีละสเต็ป

ลองไล่ k = 3, n = 7 ดูการเดินของ start และ remaining (แสดงเฉพาะ path ที่นำไปสู่คำตอบและที่ถูก prune):

def combination_sum3(k, n):
    result = []
    path = []

    def backtrack(start, remaining):
        if len(path) == k:            # เลือกครบ k ตัวแล้ว
            if remaining == 0:        # ผลรวมพอดี = คำตอบที่ใช้ได้
                result.append(path[:])
            return                    # ครบ k แล้วไม่ว่ายังไงก็หยุด
        for num in range(start, 10):  # เลือกเลขจาก start ถึง 9
            if num > remaining:       # ตัดกิ่ง: ตัวนี้และตัวถัด ๆ ใหญ่เกิน
                break
            path.append(num)                     # choose
            backtrack(num + 1, remaining - num)  # explore: ตัวถัดไปเริ่มที่ num+1
            path.pop()                           # unchoose

    backtrack(1, n)
    return result

print(combination_sum3(3, 7))  # [[1, 2, 4]]
print(combination_sum3(3, 9))  # [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
print(combination_sum3(4, 1))  # []

[[1, 2, 4]]
[[1, 2, 6], [1, 3, 5], [2, 3, 4]]
[]