Python में N को {A, B} सेट से चुने गए पूर्णांकों के योग के रूप में दर्शाने की जांच कैसे करें?

मान लीजिए हमारे पास एक संख्या target है। हमारे पास दो अन्य संख्याएं A और B हैं। हमें यह जांचना है कि क्या हम target को A और B को जितनी बार चाहें उतनी बार जोड़कर प्राप्त कर सकते हैं।

तो, यदि इनपुट Target = 26, A = 5, B = 7 है, तो आउटपुट True होगा क्योंकि हम 26 को A और B को जोड़कर प्राप्त कर सकते हैं जैसे (7 + 7 + 7 + 5)।

हल करने के चरण

• एक फ़ंक्शन util() परिभाषित करें। यह x, a, b, is_ok, target लेगा
• यदि x > target, तो:
  • वापस लौटें
• यदि is_ok[x] True है, तो:
  • वापस लौटें
• is_ok[x] := True
• util(x + a, a, b, is_ok, target)
• util(x + b, a, b, is_ok, target)
• मुख्य विधि से निम्नलिखित करें:
  • is_ok := आकार (target + 1) की एक सरणी और False से भरें
  • util(0, a, b, is_ok, target)
  • is_ok[target] लौटाएं

उदाहरण

def util(x, a, b, is_ok, target):
    if x > target:
        return
    if is_ok[x]:
        return
    is_ok[x] = True
    util(x + a, a, b, is_ok, target)
    util(x + b, a, b, is_ok, target)

def solve(target, a, b):
    is_ok = [False] * (target + 1)
    util(0, a, b, is_ok, target)
    return is_ok[target]

target = 26
A = 5
B = 7
print(solve(target, A, B))

इनपुट

26, 5, 7

आउटपुट

True