Program Explanation

The Subset Sum Problem involves determining whether there exists a subset of a given set of integers
that sums to a specified target value. This program utilizes dynamic programming to solve the problem
efficiently. It constructs a table that keeps track of achievable sums for various subsets of the input
set.

Program Structure

1. Function Definition: The main function is isSubsetSum(set []int, sum int) bool,
   which takes an array of integers and the target sum as input and returns a boolean indicating
   whether a subset with the given sum exists.
2. Dynamic Programming Table: A 2D slice dp is created to store boolean values
   indicating whether a particular sum is achievable with the first `i` items of the set.
3. Logic: Nested loops iterate through the set and sums:
   • The first column is initialized to true (0 sum is always achievable).
   • For each item, the program checks if the current sum can be formed by either including
     or excluding the current item.
4. Result: The existence of a subset with the given sum is determined from the bottom-right
   cell of the DP table.

Go Code

package main

import (
    "fmt"
)

// isSubsetSum determines if there is a subset with a given sum.
func isSubsetSum(set []int, sum int) bool {
    n := len(set)
    
    // Create a DP table to store subset sums
    dp := make([][]bool, n+1)
    for i := range dp {
        dp[i] = make([]bool, sum+1)
    }
    
    // Initialize the first column, as sum 0 can always be achieved
    for i := 0; i <= n; i++ {
        dp[i][0] = true
    }
    
    // Fill the DP table
    for i := 1; i <= n; i++ {
        for j := 1; j <= sum; j++ { if set[i-1] > j {
                dp[i][j] = dp[i-1][j] // Exclude the item
            } else {
                dp[i][j] = dp[i-1][j] || dp[i-1][j-set[i-1]] // Include or exclude the item
            }
        }
    }
    
    // The answer is in the bottom-right cell
    return dp[n][sum]
}

func main() {
    // Example set and sum
    set := []int{3, 34, 4, 12, 5, 2}
    sum := 9
    
    if isSubsetSum(set, sum) {
        fmt.Println("A subset with the given sum exists.")
    } else {
        fmt.Println("No subset with the given sum exists.")
    }
}

Explanation of the Code:

• Function isSubsetSum(set []int, sum int) bool:
  • This function checks if a subset with a specific sum exists in the given set of integers using dynamic programming.
  • It initializes a 2D slice dp, where dp[i][j] is true if a sum j can be achieved with the first i items of the set.
• Dynamic Programming Table (dp):
  • The dimensions of the dp table are (n+1) x (sum+1), where n is the number of items in the set.
  • The first column is initialized to true, indicating that a sum of 0 is always achievable (with an empty subset).
• Logic for Filling the DP Table:
  • For each item in the set, the program checks if the current item’s weight exceeds the current sum j.
  • If it does, the item cannot be included, and the value from the previous row (dp[i-1][j]) is carried forward.
  • If the item can be included, the program checks both possibilities: including the item or excluding it, updating dp[i][j] accordingly.

How to Run the Program:

1. Save the code as main.go.
2. Open your terminal and navigate to the directory containing the file.
3. Run the command go run main.go.

This program effectively demonstrates the solution to the subset sum problem using dynamic programming and can be a useful reference for applications in various domains, including finance and optimization tasks.

Conclusion

This Go program effectively determines whether a subset with a given sum exists in a set of integers
using dynamic programming. The algorithm has a time complexity of O(n * sum), where n is the number of
elements in the set. This method can be applied in various scenarios, such as resource allocation
and solving combinatorial problems.