Backtracking on Subset Sum Problem

    Step 1: Start with an empty subset and a sum of zero.
    Step 2: For each number, decide to include it in the subset or not.
    Step 3: If the sum of the current subset equals the target sum, a solution is found.
    Step 4: If the sum exceeds the target or all numbers are considered, backtrack.
    Step 5: Repeat until all subsets are explored.
  

      import java.util.ArrayList;
      import java.util.List;

      public class SubsetSum {
          static void findSubsets(int[] nums, int target) {
              List current = new ArrayList<>();
              backtrack(nums, target, 0, current);
          }

          static void backtrack(int[] nums, int target, int start, List current) {
              if (target == 0) {
                  System.out.println(current);
                  return;
              }
              if (target < 0) return;

              for (int i = start; i < nums.length; i++) {
                  current.add(nums[i]);
                  backtrack(nums, target - nums[i], i + 1, current);
                  current.remove(current.size() - 1);
              }
          }

          public static void main(String[] args) {
              int[] nums = {3, 34, 4, 12, 5, 2};
              int target = 9;
              findSubsets(nums, target);
          }
      }
    

[4, 5]
[3, 4, 2]