Class SubsetsGivenSum

java.lang.Object
topics.backtracking.subsetsum.SubsetsGivenSum
public class SubsetsGivenSum extends Object

Subset Sum

This class identifies all possible subsets of a given array of strictly positive integers whose elements sum up to a specific target value. It utilizes a Backtracking algorithm with an inclusion/exclusion branching model.

Complexity

  • Time Complexity: O(2N) - The state space tree models a binary choice (include or exclude) for each of the N elements. Pruning drastically reduces the physical paths explored.
  • Space Complexity: O(N) - Dictated by the memory required to maintain the boolean tracking array and the maximum depth of the JVM call stack.
Author:
vicegd

  • Constructor Details

    • SubsetsGivenSum

      public SubsetsGivenSum(int[] elements, int targetSum)
      Initializes the Subset Sum solver.
      Parameters:
      elements - An array of positive, distinct integers representing the mathematical set.
      targetSum - The exact cumulative sum required for a subset to be considered a valid solution.

  • Method Details

    • solve

      public void solve()
      Triggers the backtracking execution to find all valid subsets.

    • getSolutionCount

      public int getSolutionCount()
      Retrieves the total count of valid subsets discovered by the algorithm.
      Returns:
      The integer count of valid solutions.