Question about stringstream

[ccy2059]

#include <iostream>
#include <sstream>

using namespace std;

bool subsetsum(int *array, int n, int target, stringstream & ss) {
  // base cases:
  if (target == 0)
    return true;

  if (n == 0)
    return false;

  // progress
  if (subsetsum(array, n - 1, target, ss)) {  
    return true;
  }
  else if (subsetsum(array, n - 1, target - array[n-1], ss)) {
    ss << " " << array[n-1];
    return true;
  }

  return false;
}


int main() {
  int n;
  int *array;
  int target;

  // getting the input.
  cin >> n;
  array = new int[n];
  for (int i = 0; i < n; ++i)
    cin >> array[i];
  cin >> target;

  stringstream ss;
  if (subsetsum(array, n, target, ss))
    cout << "Group:" << ss.str() << endl;
  else 
    cout << "Not found!" << endl;
}

The above program is finding the subset sum of the input numbers.
n stands for the number of input, array[] holding the n numbers and target stands for the target sum.

The program finds a group of integers that can sum up to target, or print “not found” otherwise.

I cannot understand how the stringstream ss works in this program,
I do not know which is the initial value of ss when the program is called and how the numbers are stored in it.
Can anyone explain to me?

[hamsterman]

A stringstream is a special kind of string that allows writing to it and reading form it as if it was a file or console. It's initial value is "". Line 19 appends one number to the string. Line 41 prints the contents of this string.

Is that enough or should I explain the algorithm itself?

[ccy2059]

Thank you.
However, I still don't know how the program works.
Could you explain the algorithm?

[hamsterman]

Let's say, you have numbers A B C D and a target T. The algorithm considers two cases. The last number either is or isn't included in the sum. If it isn't (line 15), then you have to check if numbers A B C can add up to T (a recursive call). If it is (line 18), D + some of A B C have to add up to T. Using obvious maths, this means that numbers A B C have to add up to T - D (another recursive call). The process stops when T is 0, which means that all the numbers you subtracted from T add up to T, or when you run out of array elements (n = 0).

Notice that the same stringstream object is being passed around. For simplicity, you may not use it at all and write to cout instead. This is safe (won't produce wrong results) because you only write things after you've found the sum.

[ccy2059]

As you have said, the process stops when T is 0 or when I run out of array elements (n = 0).
Then does line 23(return false) useful in the program and how it works if it is useful?

And you mean I can just delete ( ss << " " << array[n-1]; )and change it to a simple cout (cout << array[n-1]) statement without using the stringstream?

[hamsterman]

Line 23 is useful. Try seeing how the algorithm works is array is {1} and target = 5. All ifs will be ignored.

You can really remove the stringstream. Notice that then "Group:" will be printed after the numbers.

[ccy2059]

It is used to terminate the function and return false for case "NOT found!", right ?

And isn't it stringstream ss cannot printed by cout << ss but can printed only by bout << ss.str() ?

[hamsterman]

The last return is reached (assuming failure) on all calls to subsetsum except the one where n = 0.

You're right cout << ss won't give what you want. ss.str() and, I think, ss.rdbuf() can be used for that. Don't really see why you ask that, though..

[ccy2059]

I asked that because I am not so familiar with stringstream, not related to the program actually...
Thank you very much for your help, I understand the program now.