My issue
The Code showing as Timelimit exceeded while submitting
My code
def subset_sum_dynamic_programming(numbers, target_sum):
n = len(numbers)
# Create a 2D table to store the subproblem results
dp = [[False for _ in range(target_sum + 1)] for _ in range(n + 1)]
# Base case: For a target sum of 0, it's always possible to have an empty subset
for i in range(n + 1):
dp[i][0] = True
# Tabulation - fill up the table using dynamic programming
for i in range(1, n + 1):
for j in range(1, target_sum + 1):
if numbers[i - 1] <= j:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - numbers[i - 1]]
else:
dp[i][j] = dp[i - 1][j]
# Backtrack to find the subset that adds up to the target sum (if it exists)
subset = []
i, j = n, target_sum
while i > 0 and j > 0:
if dp[i][j] and not dp[i - 1][j]:
subset.append(numbers[i - 1])
j -= numbers[i - 1]
i -= 1
return subset if dp[n][target_sum] else None
t = int(input())
for _ in range(t):
X, N = map(int, input().split())
A = list(map(int, input().split()))
result = subset_sum_dynamic_programming(A, X)
if result:
print('Yes')
else:
print('No')
Learning course: Kalasalingam Academy of Research and Education
Problem Link: CodeChef: Practical coding for everyone