Problem Statement

The Subset Sum Problem is a classic algorithmic problem in computer science. It asks whether a subset of a given set of integers can sum up to a specified target value. This problem is a well-known NP-complete problem.

Approach Explanation

This problem can be solved using dynamic programming. The idea is to build a table that keeps track of which sums can be achieved with subsets of the input set.

Dynamic Programming Structure:

1. Define a 2D DP table where dp[i][j] represents whether a sum of j can be achieved with the first i items of the input set.
2. Initialize the first column of the table to True, as a sum of zero can always be achieved with an empty subset.
3. Iterate through the table, filling it based on whether to include the current item in the subset or not.
4. The final answer will be found in dp[n][target], where n is the number of items and target is the desired sum.

Time Complexity:

O(n * target), where n is the number of items and target is the target sum.

Space Complexity:

O(n * target) for the DP table.

Python Code

def is_subset_sum(nums, target):
    """
    Function to determine if a subset with a given sum exists.

    Args:
    nums (List[int]): List of integers representing the set.
    target (int): The target sum to check for a subset.

    Returns:
    bool: True if a subset with the given sum exists, False otherwise.
    """
    n = len(nums)
    
    # Create a DP table initialized to False
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    
    # Initialize the first column (sum 0 is always achievable)
    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 nums[i - 1] <= j:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[n][target]


# Example usage
numbers = [3, 34, 4, 12, 5, 2]
target_sum = 9
exists = is_subset_sum(numbers, target_sum)

print("Subset with the given sum exists:", exists)
    

Explanation of the Program

Let’s break down the structure of the program:

1. Input:

The input consists of a list of integers and a target sum:

    numbers = [3, 34, 4, 12, 5, 2]
    target_sum = 9

2. DP Table Initialization:

A DP table is created with dimensions (n + 1) x (target + 1), initialized to False. This table is used to store whether a sum can be achieved with subsets of the input set.

3. Base Case Setup:

The first column of the DP table is initialized to True, indicating that a sum of zero is always achievable (using the empty subset).

4. Filling the DP Table:

The program iterates through each number and possible sums. If the current number can be included in the sum, the program updates the DP table to reflect whether the sum can be achieved by either including or excluding the number.

5. Final Result:

The existence of a subset that sums up to the target is indicated in the cell dp[n][target].

Example Execution:

For the provided input, the output will indicate whether a subset with the given sum exists:

Subset with the given sum exists: True

This indicates that there exists a subset of the numbers that adds up to the target sum of 9.