מספר אופנים ליצירת שרשרת

צורף מכין שרשרת ארוכה ממקטעי שרשראות קצרות אותן הוא מחבר זו לזו. הוא רוצה ליצור שרשרת באורך k ס"מ. ויכול לקחת מכל אורך כמה מקטעים שירצה, אבל בסך הכל יכול לקחת num מקטעי שרשראות לכל היותר.

בהינתן מספר המקטעים המקסימלי המותר num, ואת האורכים האפשריים של המקטעים lengths. יש להחזיר את מספר האופנים בהם ניתן ליצור שרשרת באורך k.

לדוגמה, אם נתון ש:

  • הסוגים השונים של מטבעי השרשראות הם באורכים (סנטימטרים) 2, 5, 10, 20, 50
  • אורך השרשרת הרצויה הוא 40 ס"מ
  • מותר לצורף לקחת עד 4 מקטעים בלבד

אזי האפשרויות להדבקת המקטעים הן:

  • 20 + 20 (2 מקטעים)
  • 10 + 10 + 20 (3 מקטעים)
  • 5 + 5 + 10 + 20 (4 מקטעים)
  • 10 + 10 + 10 + 10 (4 מקטעים)

ולכן יוחזר הערך 4.

השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.

אילוצים:

המערך מכיל מספרים שלמים חיוביים (ממש) בלבד והוא אינו ממוין.

דוגמה 1:
קלט: 
lengths = [2, 5, 10, 20, 50],
k = 40,
num = 4
פלט: 
4

הסבר: ישנן 4 דרכים ליצור שרשרת באורך 40 ס"מ עם עד 4 מקטעים.

דוגמה 2:
קלט: 
lengths = [1, 2, 3],
k = 4,
num = 2
פלט: 
2

הסבר: ישנן 2 דרכים ליצור שרשרת באורך 4 ס"מ עם עד 2 מקטעים: 1+3 ו-2+2.

דוגמה 3:
קלט: 
lengths = [5, 10, 25],
k = 30,
num = 3
פלט: 
2

הסבר: ישנן 2 דרכים ליצור שרשרת באורך 30 ס"מ עם עד 3 מקטעים: 5+25 ו-10+20.

דוגמה 4:
קלט: 
lengths = [1, 2],
k = 3,
num = 3
פלט: 
2

הסבר: ישנן 2 דרכים ליצור שרשרת באורך 3 ס"מ עם עד 3 מקטעים: 1+1+1 ו-1+2.

דוגמה 5:
קלט: 
lengths = [2, 3, 7],
k = 12,
num = 4
פלט: 
2

הסבר: ישנן 2 דרכים ליצור שרשרת באורך 12 ס"מ עם עד 4 מקטעים: 3+3+3+3 ו-2+2+2+2+2+2.

דוגמה 6:
קלט: 
lengths = [1, 5, 10],
k = 15,
num = 3
פלט: 
2

הסבר: ישנן 2 דרכים ליצור שרשרת באורך 15 ס"מ עם עד 3 מקטעים: 5+10 ו-5+5+5.

דוגמה 7:
קלט: 
lengths = [3, 6, 9],
k = 18,
num = 2
פלט: 
1

הסבר: ישנה דרך אחת ליצור שרשרת באורך 18 ס"מ עם עד 2 מקטעים: 9+9.

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

קלט:

lengths = [2, 5, 10, 20, 50],
k = 40,
num = 4

הפלט המבוקש:

4