צריכה לכתוב תכנית המקבלת קלט של קבוצה, וערך סכום.

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

לדוגמא:

קלט:

[1,2,5,3,2] :קבוצה

ערך סכום: 5

פלט:

[1,2,2]

[2,3]

[5]

[3,2]

איך עושים את זה?

שאלה קלאסית המזמינה רקורסיה, או ספציפית יותר במקרה הזה backtracking.

הרעיון בגדול הוא לפתור את הבעיה ה"גדולה" באמצעות פתרון תת בעיות קטנות יותר המוכלות בבעיה הכללית.

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

אולי יש פתרונות טובים/קצרים יותר אבל זה עובד (כתוב ב c#) :

static void Main(string[] args)
{
  int[] group = Array.ConvertAll<string, int>(Console.ReadLine().Split(','), delegate(string s) { return int.Parse(s); });
  int sum = int.Parse(Console.ReadLine());

  for (int i = 0; i < group.Length; i++)
  {
    LinkedList<int> subGroup = new LinkedList<int>();
    subGroup.AddFirst(group[i]);
    PrintSolutions(group, i, sum, subGroup, group[i]);
  }
}

private static void PrintSolutions(int[] group, int pos, int usum, LinkedList<int> curSubGroup, int curSum)
{
  if (curSum == usum)
    PrintSolutionsList(curSubGroup);
  else if (curSum < usum)
  {
    for (int i = pos + 1; i < group.Length; i++)
    {
      curSubGroup.AddLast(group[i]);
      PrintSolutions(group, i, usum, curSum + group[i], curSubGroup);
    }
  }
  else
    items.RemoveLast();
}

private static void PrintSolutionsList(LinkedList<int> list)
{
  for (LinkedListNode<int> p = list.First; p != null; p = p.Next)
    Console.Write(p.Value + " ");
  Console.WriteLine();
}

הסבר:

PrintSolutions מקבלת מערך (הקבוצה) המיקום הנוכחי שממנו יש להתחיל (pos), הסכום שהמשתמש הכניס (usum), תת הקבוצה הנוכחית שנבדקת (curSubGroup) והסכום של תת הקבוצה הונוכחית שנבדקת (curSum).

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

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

יש למשיהו מושג איך פותרים את זה בפרולוג???

(מתי אני משתמשת ב!? מה התנאי עצירה? ומתי הוא מדפיס לי את התתי מחרוזות?)