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

צירפתי תמונה עם השאלה במלואהhttps://2011-uploaded.fresh.co.il/2...30/18864874.jpg


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

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

תודה מראש לכל מי שמקדיש מזמנו.

בס"ד

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

קוד:

int find_sub_sequence(int *arr,int *sub,int size,int sum) {
	if (!sum) return 1;
	if (!size) return 0;
	if (find_sub_sequence(arr+1,sub+1,size-1,sum)) return 1;
	if (find_sub_sequence(arr+1,sub+1,size-1,sum-*arr)) return *sub=1;
	return 0;
}

האם הקוד הזה מטפל במקרים בהם הקומבינציה מורכבת מאיברים שלא בהכרח סמוכים זה לזה? כי אני לא רואה את זה...

בס"ד

למה לא?
הקריאה עם כל המערך קוראת לפונקציה על הזנב ה-1, שקוראת לפונקציה על הזנב ה-2, וכו'...

עריכה: בדקתי את הקוד, והוא עובד על המערך שבדוגמא.

רגע מה זה כל הכוכביות האלה?

המפרט שנתנו לנו הוא חובה... אי אפשר לשנות את חותמת הפונקציה...

תרגיש חופשי לשנות את החותמת ל - []int arr[],int sub
ובאותה הזדמנות ללמוד על מצביעים.

ציטוט:

במקור נכתב על ידי Michael Shermer Smart people are very good at rationalizing things they came to believe for non-smart reasons.

אהה... זה החומר של שבוע הבא האמת...

אני לא מבין אבל את התחביר כאן: מה ז"א נגיד
if(!sum)
return 1

מה התנאי שנבדק בתוך הסוגריים של if?

בס"ד

הבדיקה

קוד:

if(!sum)

זהה בדיוק לבדיקה

קוד:

if(sum==0)

(בהנחה ש-sum הוא int).

אגב, כשראיתי את הכותרת של ההודעה שלך ("מה זה כל הכוכביות האלה"), חשבתי שאתה מדבר על ה"הערה" ששמתי לפני הקוד.

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

בס"ד

אם כן, הסברים:

קוד:

int find_sub_sequence(int *arr,int *sub,int size,int sum)

זהה בדיוק ל:

קוד:

int find_sub_sequence(int arr[],int sub[],int size,int sum)

קטע הקוד הבא:

קוד:

if (!sum) return 1;
if (!size) return 0;

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

קוד:

*arr

הוא האיבר הראשון של arr. בדיוק כמו

קוד:

arr[0]

הרעיון של הרקורסיה הוא כזה:
נניח (לדוגמא) שהסכום המבוקש הוא 60, והאיבר הנוכחי הוא 21.
אזי, יש 2 אפשרויות לקבלת הסכום - סכום שכולל את האיבר הנוכחי, או סכום שלא כולל אותו.
כלומר, אם יש באיברים הבאים סכום של 60 או של 39.
הקריאה הרקורסיבית הראשונה בודקת 60, והקריאה השנייה בודקת 39.
אם יש סכום שלא כולל את האיבר הזה (60 בדוגמא), מספיק להחזיר 1.
אם יש סכום שכולל את האיבר הזה (39), צריך לסמן במקום המתאים ב-sub, ואז להחזיר 1.
זה מה שעושה הפקודה

קוד:

return *sub=1;

היא (כמעט) זהה לבלוק:

קוד:

{
sub[0]=1;
return 1;
}

ולסיום, אם לא מצאנו סכום מתאים, מחזירים 0.

מקווה שעכשיו הקוד מובן

Subset sum היא בעיה NP שלמה ולכן לא ידוע על פתרון שיותר טוב מפתרון מעריכי.