הדפסת כל המחרוזות הבינאריות המייצגות סכום נתון

נגדיר: מחרוזת בינארית היא מחרוזת שכל התווים בה הם '0' או '1'.

בהינתן מערך של מספרים חיוביים a, מספר שלם חיובי sum, ומחרוזת בינארית s,

נאמר כי s מציינת את הסכום sum במערך a אם התנאים הבאים מתקיימים:

  1. אורך המחרוזת s שווה לאורך המערך a.
  2. סכום האיברים שב-a באינדקסים בהם מופיע התו '1' הוא בדיוק sum.

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

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

אילוצים:

a שונה מ-null ויש בו לפחות איבר אחד.

דוגמה 1:
קלט: 
a = [1, 1, 3, 7],
sum = 8
פלט: 
0101
1001

הסבר: המחרוזות "0101" ו- "1001" מציינות את הסכום 8

דוגמה 2:
קלט: 
a = [1, 1, 3, 7],
sum = 10
פלט: 
0011

הסבר: המחרוזת "0011" מציינת את הסכום 10

דוגמה 3:
קלט: 
a = [1, 1, 3, 7],
sum = 12
פלט: 
1111

הסבר: המחרוזת "1111" מציינת את הסכום 12

דוגמה 4:
קלט: 
a = [1, 1, 3, 7],
sum = 6
פלט: 
(אין פלט)

הסבר: לא קיימת מחרוזת שמציינת את הסכום 6

דוגמה 5:
קלט: 
a = [2, 3],
sum = 3
פלט: 
01

הסבר: עבור המערך {2,3} והסכום 3, קיימת מחרוזת אחת: "01" (3=3).

דוגמה 6:
קלט: 
a = [2, 3],
sum = 2
פלט: 
10

הסבר: עבור המערך {2,3} והסכום 2, קיימת מחרוזת אחת: "10" (2=2).

דוגמה 7:
קלט: 
a = [5],
sum = 5
פלט: 
1

הסבר: עבור המערך {5} והסכום 5, קיימת מחרוזת אחת: "1" (5=5).

דוגמה 8:
קלט: 
a = [5],
sum = 0
פלט: 
0

הסבר: עבור המערך {5} והסכום 0, קיימת מחרוזת אחת: "0" (אין איברים נכללים בסכום = 0).

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

קלט:

a = [1, 1, 3, 7],
sum = 8

הפלט המבוקש:

0101
1001