Help me in solving DSSA99 problem

help
,
1

My issue

I am typed correctly but I am facing time limit exceeded please solve my problem

My code

def subset_sum_exists(arr, target):
    n = len(arr)
    
    # Create a boolean table dp where dp[i][j] represents whether a subset of
    # arr[0:i] can form the sum j.
    dp = [[False for _ in range(target + 1)] for _ in range(n + 1)]
    
    # Base case: A subset of an empty array can't form any positive sum.
    for i in range(n + 1):
        dp[i][0] = True
    
    # Fill the dp table
    for i in range(1, n + 1):
        for j in range(1, target + 1):
            # If the current element is greater than the sum j, we can't include it.
            if arr[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                # Otherwise, we can either include the current element or exclude it.
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - arr[i - 1]]
    
    # The result is in the bottom-right corner of the dp table
    return dp[n][target]

# Read the number of test cases
T = int(input())

# Process each test case
for _ in range(T):
    X, N = map(int, input().split())
    A = list(map(int, input().split()))

    # Check if there exists a subset with the given sum X
    result = "Yes" if subset_sum_exists(A, X) else "No"
    print(result)

Learning course: Kalasalingam Academy of Research and Education
Problem Link: CodeChef: Practical coding for everyone

2

Try this one. I’ve tried to optimize it a little.

def subset_sum_exists(arr, target):
    n = len(arr)
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in arr:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    
    return dp[target]

# Read the number of test cases
T = int(input())

# Process each test case
for _ in range(T):
    X, N = map(int, input().split())
    A = list(map(int, input().split()))

    # Check if there exists a subset with the given sum X
    result = "Yes" if subset_sum_exists(A, X) else "No"
    print(result)