ספירת קבוצות זרות ומשלימות

הגדרות מתמטיות:

א. גודל (size) של קבוצה (set) הוא מספר האיברים שיש בה.

למשל, בקבוצה {6, 2, 3, -5} יש ארבעה איברים, ולכן גודלה הוא 4.

ב. קבוצות זרות ומשלימות (disjoint and complementary sets) של המערך הן קבוצות שאין להן איבר משותף, והאיחוד שלהן הוא כל איברי המערך. במילים אחרות, כל איבר במערך נמצא בדיוק באחת משתי הקבוצות.

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

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

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

לדוגמה, אם המערך הוא:

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

1. {1, 2, 0, 3} {-1}
2. {1, 2, -1} {0, 3}
3. {0, 3} {1, 2, -1}
4. {1, 2, 0, 3, -1} {}
5. {1, 3} {2, 0, -1}
6. {2, 0, -1} {1, 3}
7. {1} {2, 0, 3, -1}

בחלוקה 2 למשל:

A = {1, 2, -1}

B = {0, 3}

בקבוצה A גודל הקבוצה הוא 3 סכום האיברים 2

בקבוצה B גודל הקבוצה הוא 2 סכום האיברים 3

וגם ההפרש בין הסכומים הוא 1 (|3-2|) וההפרש בין הגדלים הוא 1 (|2-3|).

בחלוקה 3 למשל:

A = {0, 3}

B = {1, 2, -1}

בקבוצה A גודל הקבוצה הוא 2 סכום האיברים 3

בקבוצה B גודל הקבוצה הוא 3 סכום האיברים 2

ההפרש בין הסכומים הוא 1 והפרש בין הגדלים הוא 1

בחלוקה 4 למשל:

A = {1, 2, 3, 0, -1}

B = {}

בקבוצה A גודל הקבוצה הוא 5 סכום האיברים 5

בקבוצה B גודל הקבוצה הוא 0 סכום האיברים 0

ההפרש בין הסכומים הוא 5 והפרש בין הגדלים הוא 5

בחלוקה 7 למשל:

A = {1}

B = {2, 0, 3, -1}

בקבוצה A גודל הקבוצה הוא 1 סכום האיברים 1

בקבוצה B גודל הקבוצה הוא 4 סכום האיברים 4

ההפרש בין הסכומים הוא 3 והפרש בין הגדלים הוא 3

אפשר לראות כי בחלוקה 1 לעיל:

A = {1, 2, 0, 3}

B = {-1}

בקבוצה A גודל הקבוצה הוא 4 סכום האיברים 6

בקבוצה B גודל הקבוצה הוא 1 סכום האיברים -1

ההפרש בין הסכומים הוא 7 והפרש בין הגדלים הוא 3

לכן חלוקה זו לא מקיימת את התנאי, ולכן היא לא תודפס ולא תיספר.

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

ההדפסה צריכה להראות כך:

1 2 0    sum = 3 count = 3
3 -1     sum = 2 count = 2

2 0 3 -1 sum = 4 count = 4
1        sum = 1 count = 1

וכן הלאה הדפסה של שאר החלוקות... הסדר לא משנה!

אם המערך הוא:

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

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

arr = [1, 2, 0, 3, -1]

1 2 0 3 -1 sum = 5 count = 5
1 2 0 sum = 3 count = 3
1 2 -1 sum = 2 count = 3
1 2 sum = 3 count = 2
1 3 -1 sum = 3 count = 3
1 sum = 1 count = 1
2 0 3 -1 sum = 4 count = 4
2 0 sum = 2 count = 2
0 3 -1 sum = 2 count = 3
0 3 sum = 3 count = 2
3 -1 sum = 2 count = 2
sum = 0 count = 0
12

arr = [1, 2, 0, 4, -1]

0

arr = [1, 1, 1, 1]

1 1 1 1 sum = 4 count = 4
1 1 1 sum = 3 count = 3
1 1 1 sum = 3 count = 3
1 1 sum = 2 count = 2
1 1 1 sum = 3 count = 3
1 1 sum = 2 count = 2
1 1 sum = 2 count = 2
1 sum = 1 count = 1
1 1 1 sum = 3 count = 3
1 1 sum = 2 count = 2
1 1 sum = 2 count = 2
1 sum = 1 count = 1
1 1 sum = 2 count = 2
1 sum = 1 count = 1
1 sum = 1 count = 1
sum = 0 count = 0
16

arr = [5, 3, 2, 0]

5 0 sum = 5 count = 2
3 2 sum = 5 count = 2
2

arr = [3, 2, 1, 0]

3 1 0 sum = 4 count = 3
3 0 sum = 3 count = 2
2 1 sum = 3 count = 2
2 sum = 2 count = 1
4

arr = [2, 2, 2, 2]

2 2 sum = 4 count = 2
2 2 sum = 4 count = 2
2 2 sum = 4 count = 2
2 2 sum = 4 count = 2
2 2 sum = 4 count = 2
2 2 sum = 4 count = 2
6

arr = [1, -1, 2, -2]

1 -1 sum = 0 count = 2
1 2 -2 sum = 1 count = 3
1 sum = 1 count = 1
-1 2 -2 sum = -1 count = 3
-1 sum = -1 count = 1
2 -2 sum = 0 count = 2
6