حلولي في كودرهب

المجموعة الفرعية المساوية

متوسط10 نقاطقوائمخوارزمياتأعدادرياضياتPythonJavaScript

الوصف

قم بكتابة دالة function تستقبل مصفوفة مكونة من اعداد صحيحة numArray،

ورقم صحيح k، تقوم هذه الدالة function بإرجاع True اذا كانت المصفوفة numArray تحتوي على مجموعة فرعية من الممكن

جمعها ليكون الناتج مساوي k و False اذا كان غير ذلك.

أمثلة

المدخلاتالمخرجات المتوقعة
numArray = [7,3,2,5,8]، k = 14true
numArray = [2,4,6,8]، k = 11false
numArray = [7,5,3,1]، k = 4true
numArray = [14,8,12,9]، k = 21true

جرّب تحله في كودرهب

الحل

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]

في هذه الصفحة