المجموعة الفرعية المساوية
متوسط10 نقاطقوائمخوارزمياتأعدادرياضياتPythonJavaScript
الوصف
قم بكتابة دالة function تستقبل مصفوفة مكونة من اعداد صحيحة numArray،
ورقم صحيح k، تقوم هذه الدالة function بإرجاع True اذا كانت المصفوفة numArray تحتوي على مجموعة فرعية من الممكن
جمعها ليكون الناتج مساوي k و False اذا كان غير ذلك.
أمثلة
| المدخلات | المخرجات المتوقعة |
|---|---|
numArray = [7,3,2,5,8]، k = 14 | true |
numArray = [2,4,6,8]، k = 11 | false |
numArray = [7,5,3,1]، k = 4 | true |
numArray = [14,8,12,9]، k = 21 | true |
الحل
def kSumSubset(numArray: list[int], k: int) -> bool:
n = len(numArray)
dp = [[False for _ in range(k+1)] for _ in range(n+1)]
for i in range(n+1):
for j in range(k+1):
if j == 0:
dp[i][j] = True
elif i == 0:
dp[i][j] = False
else:
if numArray[i-1] <= j:
dp[i][j] = dp[i-1][j] or dp[i-1][j-numArray[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[n][k]