The Subset-Sum problem is a classic computational problem that asks whether there exists a subset of a given set of numbers whose sum is equal to a target sum. The problem can be solved using a dynamic programming approach. Here's the pseudocode for solving the Subset-Sum problem:

SubsetSum(set, targetSum):
    n = number of elements in the set
    dp = 2D array of size (n+1) x (targetSum+1)

    // Initialize the base cases
    for i = 0 to n do
        dp[i][0] = true

    for i = 1 to targetSum do
        dp[0][i] = false
    // Dynamic programming
    for i = 1 to n do
        for j = 1 to targetSum do
            if set[i-1] > j then
                dp[i][j] = dp[i-1][j]
            else
                dp[i][j] = dp[i-1][j] OR dp[i-1][j - set[i-1]]

    // Backtrack to find the subset
    if dp[n][targetSum] is false then
        return "No subset exists with the given target sum"

    subset = empty list
    i = n
    j = targetSum

    while i > 0 and j > 0 do
        if dp[i-1][j] is true then
            i = i - 1
        else
            subset.append(set[i-1])
            j = j - set[i-1]
            i = i - 1
    return subset

Let's go through the pseudocode step by step:

1. The `SubsetSum` function takes a set of numbers and a target sum as input and returns a subset that sums up to the target sum.

2. It initializes a 2D array `dp` of size `(n+1) x (targetSum+1)` to store the dynamic programming results.

3. The base cases are set up such that if the target sum is 0, then there is always an empty subset that sums up to 0. Therefore, `dp[i][0]` is set to `true` for all `i`.

4. For the rest of the `dp` array, the initial values are set to `false`.

5. The dynamic programming part fills in the `dp` array using a nested loop. For each element in the set and each possible target sum, it checks whether including or excluding the current element can lead to the target sum.

6. If the current element `set[i-1]` is greater than the target sum `j`, then it cannot be included in the subset. Hence, `dp[i][j]` takes the value of `dp[i-1][j]`, indicating the result without including the current element.

7. If the current element `set[i-1]` is less than or equal to the target sum `j`, then it can be either included or excluded in the subset. Hence, `dp[i][j]` takes the logical OR of `dp[i-1][j]` and `dp[i-1][j - set[i-1]]`, indicating whether either of the two possibilities leads to the target sum.

8. After the dynamic programming step, if `dp[n][targetSum]` is `false`, it means no subset exists with the given target sum, so the function returns an appropriate message.

9. If a subset exists, the function backtracks to reconstruct the subset. It starts from the last element of the set and the target sum and checks whether the current element was included in the subset.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc