This function generates the subsets of a set that sums up to K using the naive brute force approach but also backtracking when necessary

subset_sum_backtracking.java

    private static List<Integer> elements;
    private static List<List<Integer>> subsetsWithSumK;
    private static List<Integer> currentSubset;

    private static int numberOfElements, methodCalls;

    private static List<List<Integer>> subsetSum(int sumK, List<Integer> elementsArg) {
        elements = elementsArg;
        numberOfElements = elements.size();
        subsetsWithSumK = new ArrayList<>();
        currentSubset = new ArrayList<>();

        methodCalls = 0;
        _subsetSum(0, sumK);

        System.out.println(String.format("Subsets of %s with sum %d: %s. \nMethod calls: %d\n", elements,  sumK, subsetsWithSumK, methodCalls));

        return subsetsWithSumK;
    }

    private static void _subsetSum(int index, int sumK) {
        methodCalls++;

        int currentSum = currentSubset.stream().reduce(0, Integer::sum);

        if (currentSum > sumK) {
            return;
        }

        if (index == numberOfElements) {

            if (currentSum == sumK) {
                subsetsWithSumK.add(new ArrayList<>(currentSubset)); // clone valid subset sum
            }

        } else {
            _subsetSum(index+1, sumK);
            currentSubset.add(elements.get(index));

            _subsetSum(index+1, sumK);
            currentSubset.remove(currentSubset.size()-1); // pop last element from the subset
        }
    }