418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 3

อินพุต: เซตของจำนวนเต็ม $A\,$ ที่มีสมาชิกอยู่ $n\,$ ตัว

เอาพุต: มีจำนวนเต็ม $a,b,c\in A\,$ โดยที่ $a<b<c\,$ และ $a+b>c\,$ หรือไม่

แนวคิด วัตถุที่เราต้องพิจารณาคือ จำนวนเต็ม 3 ตัวจาก จำนวนเต็มทั้งหมด $n\,$ ตัว ซึ่งในห้องเรียน เราได้เรียนวิธีในการหยิบของ $k\,$ สิ่ง จากของทั้งหมด $n\,$ สิ่งมาแล้ว ในเรื่องของ combination นั่นเอง เราจะใช้วิธีนั้นกัน ส่วนเงื่อนไขในข้อนี้คือ จำนวนเต็ม $a,b,c\,$สามตัวที่เลือกมานั้น ต้องมีคุณสมบัติว่า $a<b<c\,$ ซึ่งถ้าเลือกตามวิธีในห้องเรียน ก็จะมีคุณสมบัติดังกล่าวอยู่แล้ว ดังนั้นเงื่อนไขที่ต้องตรวจสอบจริง ๆ คือ $a+b>c\,$ หรือไม่

เวลาการทำงานของอัลกอริทึมดังกล่าวคือ ${n \choose 3}$