מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/סכום תת קבוצה/שאלה

אנא כתוב אלגוריתם יעיל המקבל כקלט מערך A של מספרים שלמים חיוביים, ומספר שלם חיובי t כלשהו, ומוציא כפלט True או False בהתאם לשאלה האם קיימת תת-קבוצה של הערכים בA שסכום איבריה הוא בדיוק t.

דוגמה: נניח שהמערך הוא $\displaystyle A=[2,1,10,40,20]$, ו$\displaystyle t=52$. התשובה היא True, מפני ש$\displaystyle 2+10+40=52$.

אנא הבע סיבוכיות תשובתך במונחי $\displaystyle n$ ו$\displaystyle t$.