Chương trình C++ kiểm tra có mua được bánh/kẹo với đúng N tiền không

Mô tả bài toán

Bánh 40đ, kẹo 70đ. Cho số N. Kiểm tra có thể mua tổ hợp bánh/kẹo tổng đúng N không.

Ví dụ

N=110. Đầu ra: True (1) (1 bánh + 1 kẹo = 110).

Thuật toán (DFS/Đệ quy)

1. Hàm dfs(i): trả true nếu có thể đạt N từ tổng hiện tại i.
2. Nếu N → false; nếu → true.
3. Thử rồi .
4. Gọi .

Đoạn mã 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;
    return 0;
}

Đầu vào / Đầu ra

Input: 110

Output: 1