โปรแกรม C++ ตรวจสอบว่าซื้อเค้กและโดนัทได้พอดีกับเงินที่มีหรือไม่

มีเงิน N บาท เค้กราคา 40 บาท โดนัทราคา 70 บาท ต้องการทราบว่าสามารถซื้อเค้กและโดนัท (รวมกันได้) ใช้เงินหมดพอดี N บาทหรือไม่

ตัวอย่าง: N=110 ผลลัพธ์: True (1) เพราะ 40+70=110

ขั้นตอนการแก้ปัญหา (DFS / Recursion)

1. ฟังก์ชัน dfs(i): เงินสะสม i
   • ถ้า i > N → false
   • ถ้า i == N → true
   • ลอง dfs(i+40) ถ้าจริง คืน true
   • มิฉะนั้นลอง dfs(i+70)
2. เรียก dfs(0)

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

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

int n;
bool dfs(int i) {
    if (i > n) return false;
    if (i == n) return true;
    if (dfs(i + 40)) return true;
    return dfs(i + 70);
}

bool solve(int N) {
    n = N;
    return dfs(0);
}

int main() {
    int N = 110;
    cout << solve(N) << endl;
}

อินพุต / เอาต์พุต

Input: 110

Output: 1