Recursive function to find combinations of elements in an array

Question

I have a larger programming problem that requires me to first be able to tell if an array contains any combination of elements that can add up to a target value.

The function I have has to have the following header:

bool sumCombination(const int a[], int size, int target);

The function must use recursion, and must not use any for loops, while loops or the word 'goto' anywhere in it. Further, I cannot use any helper functions.

Some examples of how the function works are as follows:

sumCombination([2, 4, 8], 3, 10) => true
sumCombination([2, 4, 8], 3, 12) => true
sumCombination([2, 4, 8], 3, 11) => false
sumCombination([], 0, 0)         => true

I'm not sure how to tackle this problem using recursion, and everyone that I have worked with has told me it seems impossible to do within the given parameters. I have solved this using loops. However, I am trying to solve this entirely with recursion, without using any loops.

If anyone can help me understand the logic behind this problem, I would be very grateful!

Thank you in advance!

Possible duplicate of [Subset sum variant with a non-zero target sum](https://stackoverflow.com/questions/30899356/subset-sum-variant-with-a-non-zero-target-sum) — Prune, Jul 13 '17 at 16:44

score 2 · Answer 1 · answered Jul 13 '17 at 03:58

2

bool sumCombination(const int a[], int size, int target) {
  // Can always add up to zero.
  if (!target) return true;
  // No elements to add up to anything.
  if (!size) return false;
  return
    // Try including the first element, see if tail adds up to the rest.
    sumCombination(a + 1, size - 1, target - a[0]) ||
    // Finally, try the tail alone, without the first element.
    sumCombination(a + 1, size - 1, target);
}

answered Jul 13 '17 at 03:58

Igor Tandetnik

50,461
4
56
85

What do you mean by tail? – Altairia Jul 13 '17 at 04:04
All elements of the array sans the first one. – Igor Tandetnik Jul 13 '17 at 04:05
@IgorTandetnik The solution as it is now it's not enough. You'll need to rotate the vector `size` times and try the two `tail` combinations repeatedly. As it is, the first example (`sumCombination([2, 4, 8], 3, 10)`) will return `false` instead of `true`. – Adrian Colomitchi Jul 13 '17 at 04:10
I also didn't understand the "||". How can a function choose to return one of two statements? – Altairia Jul 13 '17 at 04:15
@Altairia May I humbly suggest you read about logical operators in your favorite C++ textbook. – Igor Tandetnik Jul 13 '17 at 04:16
@IgorTandetnik Right. +1 – Adrian Colomitchi Jul 13 '17 at 04:24
I understand logical operators, this was the first time I encountered one being used this way, but I understood the truth tables. Thank you for the tip! – Altairia Jul 14 '17 at 02:32

Recursive function to find combinations of elements in an array

1 Answers1