This program demonstrates how to generate all possible subsets of a given set of integers that sum up to a specified target value.

Program Code

  package main

  import (
      "fmt"
  )

  // Function to find all subsets with a given sum
  func findSubsets(arr []int, target int) [][]int {
      var result [][]int
      var current []int

      // Helper function to perform the backtracking
      var backtrack func(int, int)
      backtrack = func(index int, currentSum int) {
          // If the current sum equals the target, add the subset to the result
          if currentSum == target {
              subset := make([]int, len(current))
              copy(subset, current)
              result = append(result, subset)
              return
          }

          // If the sum exceeds the target, no need to explore further
          if currentSum > target {
              return
          }

          // Explore further subsets
          for i := index; i < len(arr); i++ {
              current = append(current, arr[i])  // Include the current element
              backtrack(i+1, currentSum+arr[i])  // Explore next index with updated sum
              current = current[:len(current)-1]  // Backtrack and remove the current element
          }
      }

      // Start the backtracking process
      backtrack(0, 0)
      return result
  }

  // Main function
  func main() {
      arr := []int{1, 2, 3, 4, 5}
      target := 5

      fmt.Printf("Given array: %v\n", arr)
      fmt.Printf("Target sum: %d\n", target)

      subsets := findSubsets(arr, target)

      // Print all the subsets that add up to the target sum
      fmt.Println("Subsets with sum", target, ":")
      for _, subset := range subsets {
          fmt.Println(subset)
      }
  }
  

Program Explanation

The goal of this program is to generate all subsets of a given array of integers that sum up to a target value. We accomplish this through backtracking.

• findSubsets function: This function takes an array and a target sum as input, and returns a 2D slice where each element is a subset of the array that sums up to the target. It uses a helper function backtrack to explore the possible subsets.
• backtrack function: A recursive helper function that uses backtracking to explore all possible subsets. It tries to add each element starting from the current index to the current subset. If the sum of the subset matches the target, the subset is added to the result.
• Base Case: When the sum of the current subset equals the target, the subset is copied and added to the result. If the sum exceeds the target, the function returns without exploring further possibilities.
• Backtracking: After exploring the current subset, the element is removed (backtracked) and the algorithm proceeds to the next index, ensuring that all possible subsets are explored.

Program Flow

1. The program starts by initializing an array and a target sum.
2. It calls the findSubsets function, which triggers the backtrack process.
3. The backtrack function recursively builds subsets and checks whether the current sum matches the target.
4. Whenever a valid subset is found, it is added to the result array.
5. The program finally prints all subsets that add up to the target sum.

Sample Output

For the array [1, 2, 3, 4, 5] and target sum 5, the output would be:

  Given array: [1 2 3 4 5]
  Target sum: 5
  Subsets with sum 5 :
  [1 4]
  [2 3]
  [5]

Time and Space Complexity

Time Complexity: The time complexity is O(2^n), where n is the number of elements in the input array. This is because, in the worst case, the algorithm has to explore all possible subsets of the array.

Space Complexity: The space complexity is O(n) for the recursion stack, where n is the depth of the recursion (the number of elements in the array).

Explanation:

• Code Structure:
  • The program consists of two main functions: findSubsets and backtrack.
  • findSubsets is the main function that initiates the backtracking process and manages the subsets.
  • backtrack is a helper function that recursively builds subsets and checks if they meet the target sum.
  • The main function initializes the array and the target, calls findSubsets, and prints the results.
• Backtracking Approach:
  • It builds subsets by including elements one by one, checking if the current subset’s sum matches the target.
  • If the sum exceeds the target, further exploration of that subset is stopped.
  • Once a valid subset is found, it’s added to the result.