मान लीजिए हमारे पास एक संख्या N है। एक केक विक्रेता 40 रुपये में केक और 70 रुपये में डोनट बेच रहा है। हमें जाँचना है कि क्या हम उनमें से कुछ को ठीक N रुपये में खरीद सकते हैं या नहीं।
उदाहरण के लिए, यदि इनपुट है N = 110, तो आउटपुट True होगा, क्योंकि 40 + 70 = 110।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
o := false
एक फंक्शन dfs() परिभाषित करें जो i लेता है:
यदि i > n, तो false लौटाएँ
यदि i == n, तो true लौटाएँ
यदि dfs(i + 40) सत्य है, तो true लौटाएँ
dfs(i + 70) लौटाएँ
मुख्य विधि से:
n := N
o := dfs(0)
o लौटाएँ
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int n; bool o = false; 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; o = dfs(0); return o; } int main(){ int N = 110; cout << solve(N) << endl; }
इनपुट
110
आउटपुट
1
