หาจำนวนวิธีแสดงจำนวนเต็มเป็นผลรวมของ n-th power ของจำนวนธรรมชาติที่ไม่ซ้ำใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะหาจำนวนวิธีที่จำนวนเต็ม number สามารถเขียนในรูปผลรวมของ n-th power ของจำนวนธรรมชาติที่ ไม่ซ้ำกัน (unique) ได้

ตัวอย่าง

Input: number = 50, power = 2
Output: 3
วิธีที่เป็นไปได้สำหรับ 50 = 1²+7², 5²+5² (ไม่ได้เพราะซ้ำ), 1²+3²+... → จริงๆ มี 3 วิธี

อัลกอริทึม: Recursion + Backtracking

ลองทุกชุดย่อยของจำนวนธรรมชาติ 1, 2, 3, ... ที่ยกกำลัง power ไม่เกิน number

ขั้นตอนการแก้ปัญหา

1. กำหนด number และ power
2. เขียนฟังก์ชันเรียกซ้ำ รับพารามิเตอร์: number, power, i (จำนวนปัจจุบันที่ลอง)
3. Base cases:
   • number < 0 หรือ i^power > number → return 0
   • number == 0 หรือ i^power == number → return 1 (พบวิธีหนึ่ง)
4. Recursive case: ผลรวมของ 2 กรณี
   • นำ i^power ไปใช้: f(number - i^power, power, i+1)
   • ไม่ใช่ i: f(number, power, i+1)

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

#include <bits/stdc++.h>
using namespace std;

int findPossibleWaysCount(int number, int power, int i = 1) {
    if (number < 0 || number < pow(i, power)) return 0;
    if (number == 0 || number == pow(i, power)) return 1;
    
    return findPossibleWaysCount(number - pow(i, power), power, i + 1) +
           findPossibleWaysCount(number, power, i + 1);
}

int main() {
    int number = 50, power = 2;
    cout << findPossibleWaysCount(number, power) << endl;
    return 0;
}

ผลลัพธ์

3

หมายเหตุประสิทธิภาพ

อัลกอริทึมนี้เป็น exponential time สำหรับ number ใหญ่ควรใช้ Dynamic Programming (Memoization) หรือ DP Bottom-up เพื่อลดการคำนวณซ้ำ

สรุป

ใช้ Recursion หาจำนวนวิธีแยกจำนวนเป็นผลรวมกำลัง n ของจำนวนธรรมชาติไม่ซ้ำ หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ