CODEWITHSUNDEEP
algorithmcombinationssubsetsubset-sum
Darth.Vader
Darth.Vader

Reputation: 6271

subset sum from recursive backtracking

I am trying to modify the "List all combinations in a string" question, to a problem where we need to print all sets that have a given 'sum'. Here is my initial Code, but I am not sure how I can save the list of sets in the code:

/**
 * method to return  all sets with a given sum.
 **/
public static List<List<Integer>> lists = new ArrayList<>();
public static List<Integer> list = new ArrayList<Integer>();
public static void countSubsetSum3(int arr[], int k, int sum) {
    if(sum == 0) {
        return;
    }
    if(sum != 0 && k == 0) {
        return;
    }
    if(sum < arr[k - 1]) {
        countSubsetSum3(arr, k-1, sum);
    }
    countSubsetSum3(arr, k-1, sum - arr[k-1]);
    countSubsetSum3(arr, k-1, sum);
}

How can we modify this code to make it print all possible sets that have the sum 'sum'. Thanks!

Upvotes: 1

Views: 2360

Answers (1)

welter
welter

Reputation: 166

You have to return from your function when string's length is 0. Right now you're just printing your prefix and then the line:

subset(prefix + string.charAt(0), string.substring(1));

is executed, which raises StringIndexOutOfBoundsException because you're calling .substring(1) on an empty string.

Upvotes: 2

Related Questions