סדרה סופר עולה

נסמן סדרת מספרים טבעיים באורך n כך: (a1, a2, a3, ... , an).
נגדיר: סדרה נקראת סופר עולה אם כל איבר בסדרה גדול מסכום האיברים שקדמו לו.

כלומר לכל 1 ≤ i < n מתקיים ai+1 > a1 + a2 + ... + ai.
בהינתן סדרה סופר עולה (a1, a2, a3, ... , an) ומספר שלם target יש לבדוק האם קיימת תת-קבוצה של האיברים {a1, a2, a3, ... , an} שסכום איבריה הוא בדיוק target.
שימו לב, התת-קבוצה יכולה לכלול איברים כלשהם, לאו דווקא איברים רצופים בסדרה. כל איבר בסדרה יכול להופיע בתת-הקבוצה פעם אחת בלבד.
יש להחזיר true אם קיימת במערך תת-קבוצה שסכום איבריה הוא בדיוק target, אחרת false.

השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.

אילוצים:
  • במערך יש סדרה סופר-עולה.
דוגמה 1:
קלט: 
nums = [2, 3, 8, 27],
target = 30
פלט: 
true

הסבר: יש תת-קבוצה העונה על הדרישות והיא {3, 27}.

דוגמה 2:
קלט: 
nums = [2, 3, 8, 27],
target = 7
פלט: 
false

הסבר: אין תת-קבוצה העונה על הדרישות כיוון ש-{2, 2, 3} אינו פתרון חוקי.

דוגמה 3:
קלט: 
nums = [],
target = 0
פלט: 
true

הסבר: יש תת-קבוצה שהיא הקבוצה הריקה.

דוגמה 4:
קלט: 
nums = [2, 3, 8, 27],
target = -1
פלט: 
false

הסבר: אין תת-קבוצה; כל האיברים טבעיים, הסכום חיובי תמיד.

דוגמה 5:
קלט: 
nums = [1, 3, 6, 13, 27, 52],
target = 40
פלט: 
true

הסבר: יש תת-קבוצה העונה על הדרישות והיא {13, 27}. הסדרה היא סופר עולה כי כל איבר גדול מסכום האיברים שקדמו לו.

דוגמה 6:
קלט: 
nums = [1, 2, 4, 8, 16, 32, 64],
target = 82
פלט: 
true

הסבר: יש תת-קבוצה העונה על הדרישות והיא {2, 16, 64}. הסדרה היא סופר עולה כי כל איבר גדול מסכום האיברים שקדמו לו (סדרה גיאומטרית עם יחס 2).

דוגמה 7:
קלט: 
nums = [1, 3, 10, 30, 100],
target = 85
פלט: 
false

הסבר: אין תת-קבוצה שסכום איבריה הוא בדיוק 85. האפשרויות הקרובות ביותר הן 84 = 1 + 3 + 10 + 30 + 40 או 100.

דוגמה 8:
קלט: 
nums = [3, 11, 21, 70, 210, 700, 2100],
target = 1024
פלט: 
false

הסבר: אין תת-קבוצה שסכום איבריה הוא בדיוק 1024. בסדרה סופר עולה, כאשר מפעילים את האלגוריתם הבודק מהסוף להתחלה ולא מוצאים סכום מדויק, התשובה היא שלילית.

Loading...
נשמרLn 1, Col 1

קלט:

nums = [2, 3, 8, 27],
target = 30

הפלט המבוקש:

true