trying to write a recursive function that counts the number of sequences that sum up to that number C++

Question

Okay, so here is what I'm trying to do. The user inputs a number. I'm trying to write a recursive function that counts the number of sequences that sum up to that number (user input).

For example:

Then the number of sequences that sum up to 6 is 11 (including 6 itself).

6
5+1
4+1+1
3+1+1+1
2+1+1+1+1
1+1+1+1+1+1
2+2+1+1
3+2+1
4+2
2+2+2
3+3

I'm also trying not to have sequences that repeat, for example 2+2+1+1 and 1+1+2+2.

The reason i have no code included is i cannot figure out a recursive way to make this work so i'm seeking some guidance. Thanks in advance!

ADDITION:

Okay so here is what my thought process is. 6 can be split as...

6
5+1
4+2
3+3

but it is still not over,if you take 5+1 and consider the +1 part to be completed; you use the same trick to proceed.

4+1+1
3+2+1

but then they start to repeat..... and i don't get further than this second step in my plan.

Okay so code wise this is what I've come up with on my own. Looking for suggestions to fix this.

int sum(int number, int min, int counter)
{
    int temp=0, n;
    n=number+temp;
    if (number>=(n/2)& number!=min)
    {
        while (number>=(n/2))
        {
            cout << number << "+"<< temp <<"\n";
            number --;
            temp ++;
            counter ++;
        }
    }
    sum(temp, 1,counter);
    return counter;
}

int main()
{
    int number;

    cout << "Please enter the number: ";
    cin >> number ;
    cout << "\n";

    sum(number, 1, 0);

    return 0;
}

I do realize this is all sorts of messed up.

Answer 1

Hint: try to find a function that gives the number of sequences with sum n and terms not larger than k.

EDIT:
Forgive me if this sounds harsh, but... your updated code is all wrong. It's hard to see what you intended. I can guess, but that would be pointless.

Here's what I had in mind: a sequence should be in nonincreasing order, like "2 2 1 1 1 1". So how many such sequences add up to 6? Well, find the number of such sequences starting with 1, then the number of sequences starting with 2, and so on up to 6, and add them up. And how many sequences start with 2 and add up to six? (This is where the recursion comes in.) In each such sequence, the first term is 2 and the rest add up to 4 with no term exceeding 2, so we must find the number of sequences adding up to 4 with no term greater than 2. So write the signature first, then the iteration loop, then the recursive call and you're done.

EDIT:
All right, here's everything but the loop:

int partition(int n, int max)
{
  if(n==0)
    return(0);
  int ret = 0;
  if(n<=max)
    ret=1;
  for(...)
  {
    ...
  }
  return(ret);
}

Can you fill in the blanks?

Answer 2

i think it is close to the probability theory
amount of combinations of set {1,2,3,4,5,6} giving summary 6

Answer 3

These are called Integer Partitions, and there is a simple way to calculate the number of partitions of any number using an intermediate function. Take a look here: Integer Partition.

Answer 4

Let f(n) be the function we want, that generates sequences of integers that add to n, without permutations

Define

f(n) = g(n,n)

g(n,p) = { i \in 1..min(n, p): [i g(n-i,i)] }

Answer 5

Define P(n) as the number of ways to partition n, restricting n to be an integer, n >= 1.

Define p(n, k) as the number of ways to partition n using numbers no larger than k, restricting k to be an integer, k >= 1, k <= n.

It follows that P(n) = sum (i: 1..n) p(n, i).

To find p(n, k), first note that we neatly avoid double-counting by simply keeping the partition sorted: take the largest chunk first. So the first chunk may have any size from 1 up to k, and then the rest of the chunks must account for the rest of the total n, and be no larger than the first chunk.

Thus p(n, k) = sum (i: 1..k) p(n - i, i).

As a base case, p(1, 1) = 1.

---

A sample implementation, very much not guaranteed to be at all efficient, or even to compile (but it should give you the basic idea) - spoilers!

// A utility function to represent the result of appending to a vector,
// as a new vector (without affecting the previous one).
template <typename T>
vector<T> operator<<(vector<T> copy, T to_append) {
    // We passed by value to get a copy implicitly.
    copy.push_back(to_append);
    return copy;
}

// A utility function to append one vector to another.
template <typename T>
vector<T>& operator+=(vector<T>& original, const vector<T>& to_append) {
    // 'copy' is in namespace std:: and defined in <algorithm>.
    // 'back_inserter' is in namespace std:: and defined in <iterator>.
    copy(to_append.begin(), to_append.end(), back_inserter(original));
    return original;
}

vector<vector<int> > partitions(int remaining, int limit, vector<int> prefix) {
    // Finds the partitions of some larger number which start with the
    // numbers in 'prefix', such that the rest of the "chunks" sum to
    // 'remaining' and are all no larger than 'limit'.

    // 'max' is in namespace std:: and defined in <algorithm>. We restrict
    // the 'limit' to be no more than 'remaining'.
    limit = max(remaining, limit);

    vector<vector<int> > result;

    // Base case. 
    if (remaining == 1) {
        return result << (prefix << 1); // note the parentheses are required!
    }

    for (int i = limit; i > 0; --i) {
        result += partitions(remaining - i, i, prefix << i);
    }

    return result;
}

Answer 6

The algorithm is well covered in this question.