CODEWITHSUNDEEP
javarecursion
user1721258
user1721258

Reputation:

A recursive algorithm to find every possible sum given an integer array?

So given an array for example [3, 5, 7, 2] I want to use recursion to give me all the possible combinations of sums, for example: 3, 5, 7, 2, 8(3+5),10(3+7),5(3+5)... 15(3+5+7) etc. I'm not exactly sure how to go about this using java.

Upvotes: 2

Views: 6886

Answers (6)

Hiren Patel
Hiren Patel

Reputation: 52800

Simplest way ever:

private int noOfSet;

Add below method:

private void checkSum() {
        List<Integer> input = new ArrayList<>();
        input.add(9);
        input.add(8);
        input.add(10);
        input.add(4);
        input.add(5);
        input.add(7);
        input.add(3);

        int targetSum = 15;
        checkSumRecursive(input, targetSum, new ArrayList<Integer>());

    }

    private void checkSumRecursive(List<Integer> remaining, int targetSum, List<Integer> listToSum) {
        // Sum up partial
        int sum = 0;
        for (int x : listToSum) {
            sum += x;
        }

        //Check if sum matched with potential
        if (sum == targetSum) {
            noOfSet++;
            Log.i("Set Count", noOfSet + "");
            for (int value : listToSum) {
                Log.i("Value", value + "");
            }
        }

        //Check sum passed
        if (sum >= targetSum)
            return;

        //Iterate each input character
        for (int i = 0; i < remaining.size(); i++) {
            // Build list of remaining items to iterate
            List<Integer> newRemaining = new ArrayList<>();
            for (int j = i + 1; j < remaining.size(); j++)
                newRemaining.add(remaining.get(j));

            // Update partial list
            List<Integer> newListToSum = new ArrayList<>(listToSum);
            int currentItem = remaining.get(i);
            newListToSum.add(currentItem);
            checkSumRecursive(newRemaining, targetSum, newListToSum);
        }
    }

Hope this will help you.

Upvotes: 0

Farah Nazifa
Farah Nazifa

Reputation: 921

public static void main(String[] args) {
    int [] A = {3, 5, 7, 2};
    int summation = recursiveSum(A, 0, A.length-1);
    System.out.println(summation);
  }

  static int recursiveSum(int[] Array, int p, int q) {
    int mid = (p+q)/2; //Base case
    if (p>q) return 0; //Base case
    else if (p==q) return Array[p];
    **else
      return  recursiveSum(Array, p, mid) +  recursiveSum(Array, mid + 1, q);**
  }

Upvotes: 0

andre
andre

Reputation: 7249

You have two choice with each number in the array.

  1. Use the number

  2. Don't use the number

    void foo(int[] array, int start, int sum) {
    if(array.length == start) return;
    int val = sum + array[start];
    //print val;
    foo(array, start + 1, val); //use the number
    foo(array, start + 1, sum); //don't use the number
}

the initial call is foo(a, 0, 0)

Upvotes: 3

Dragos Foianu
Dragos Foianu

Reputation: 9

public static void main(String[] args) {
    findAllSums(new int[] {3, 5, 7, 2}, 0, 0);
}

static void findAllSums(int[] arrayOfNumbers, int index, int sum) {     
    if (index == arrayOfNumbers.length) {
        System.out.println(sum);
        return;
    }

    findAllSums(arrayOfNumbers, index + 1, sum + arrayOfNumbers[index]);
    findAllSums(arrayOfNumbers, index + 1, sum);
}

You have two branches, one in which you add the current number and another in which you don't.

Upvotes: 0

CrazyCasta
CrazyCasta

Reputation: 28302

Here's one way of doing it in pseudo code:

getAllPossibleSums(list)
    if(list.length == 1)
        return list[0];
    otherSums = getAllPossibleSums(list[1:end])
    return union(
        otherSums, list[0] + otherSums);

Upvotes: 0

user406009
user406009

Reputation:

An recursive algorithm for this could work as follows:

All the sums for a list equals the union of:

  • The first number plus the sums of the sublist without the first number
  • The sums of the sublist without the first number

Eventually your recursive call will hit the stopping condition of an empty list, which has only one sum(zero)

Upvotes: 0

Related Questions