חלוקת מערך לשלוש קבוצות שוות סכום

נתון מערך חד-ממדי arr שערכיו הם מספרים שלמים חיוביים ממש. 

יוחזר true אם ניתן לחלק את הערכים שבמערך לשלוש קבוצות שסכומן שווה, ו-false אחרת.

שימו לב,

  • הסכום בכל קבוצה לא בהכרח נמצא בתאים צמודים זה לזה.
  • כל תא יכול להיכלל בקבוצה אחת בלבד.
  • כל אחד מהמספרים במערך צריך להיות באחת משלוש הקבוצות.
  • גודלן של שלוש הקבוצות לא צריך להיות זהה, אלא הסכומים שלהם.

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

אילוצים:

המערך אינו null ואינו ריק.

אין לשנות את תוכן המערך (אפילו לא זמנית), ולא להשתמש במערך עזר.

דוגמה 1:
קלט: 
arr = [8, 4, 7, 1, 2, 3, 5]
פלט: 
true

הסבר: ניתן לחלק את המערך לשלוש קבוצות שסכומן שווה: {8, 2}, {4, 5, 1}, {3, 7}.

דוגמה 2:
קלט: 
arr = [4, 7, 1, 2, 3, 5]
פלט: 
false

הסבר: לא ניתן לחלק את המערך לשלוש קבוצות שוות סכום.

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

הסבר: ניתן לחלק את המערך לשלוש קבוצות שוות סכום: {3, 3}, {3, 3}, {3, 3}.

דוגמה 4:
קלט: 
arr = [10, 10, 10, 10, 10, 10]
פלט: 
true

הסבר: ניתן לחלק את המערך לשלוש קבוצות שוות סכום: {10, 10}, {10, 10}, {10, 10}.

דוגמה 5:
קלט: 
arr = [1, 1, 1, 1, 1, 1, 1, 1, 1]
פלט: 
true

הסבר: ניתן לחלק את המערך לשלוש קבוצות שוות סכום: {1, 1, 1}, {1, 1, 1}, {1, 1, 1}.

דוגמה 6:
קלט: 
arr = [1, 2, 3, 4, 5, 6]
פלט: 
true

הסבר: ניתן לחלק את המערך לשלוש קבוצות שוות סכום: {1, 6}, {2, 5}, {3, 4}.

דוגמה 7:
קלט: 
arr = [1, 1, 1, 1, 1, 1, 1, 1]
פלט: 
false

הסבר: לא ניתן לחלק את המערך לשלוש קבוצות שוות סכום.

דוגמה 8:
קלט: 
arr = [2, 2, 2, 2, 2, 2, 2]
פלט: 
false

הסבר: לא ניתן לחלק את המערך לשלוש קבוצות שוות סכום.

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

קלט:

arr = [8, 4, 7, 1, 2, 3, 5]

הפלט המבוקש:

true