The algorithm for generating all numbers summed with a given number and its complexity

Question

In preparation for the interview, I discovered the following problem:

3 can be written as 1 + 1 + 1, 1 + 2, 2 + 1; 4 can be written as 1 + 1 + 1 + 1, 1 + 1 + 2, 2 + 2, 1 + 2 + 1, 2 + 1 + 1, 3 + 1, 1 + 3; Given an integer, how many possible expressions exist? (1 + 2 and 2 + 1 are different)

So it's pretty simple to write brute force algorithm to calculate this and get the set of all sets of numbers that do it:

private static Set<List<Integer>> getIntegersSum(int num) { Set<List<Integer>> returnSet = new HashSet<List<Integer>>(); if (num == 0) { returnSet.add(new LinkedList<Integer>()); return returnSet; } for (int i = 1; i <= num; i++) { Set<List<Integer>> listNMinI = getIntegersSum(num - i); for (List<Integer> l : listNMinI) { l.add(0, i); returnSet.add(l); } } return returnSet; } 

Now I believe that a recursive relation describes the complexity of this algorithm:

 T(0) = \Theta (1) T(n) = O(n) + \Sum_{i=0}^{n-1} T(i) 

I am not quite sure how to come to great difficulty from this attitude of repetition. I would also like to know if there is a closed form solution for the question (how many such combinations will we have for each issue).

I'm also not sure what the difficulty will be if we remember this algorithm by caching the results of each call (similar to how you can speed up fibonacci).

Answer 1

There are 2 ^{n - 1} - 1 such expressions.

There are several ways to solve this problem.

I am using the result of this problem:

There are sweets. How many ways are there to divide all n candies into k people (0 candies can be given)?

The order is important as the parts go to different people. Solution (n + k - 1) C (k - 1). We add k - 1 separators to the mixture (which makes the sum n + k - 1), and we are trying to find the number of ways to insert separators to divide the sweets into k parts. Think of n + k - 1 boxes in a row to place candies and dividers, and we want to find several ways to choose k - 1 slots for dividers that divide the fields into k parts.

---

Back to this problem, we need to answer this sub-problem:

How many ways to express n as the sum of k positive numbers?

We can reuse the result from the problem of splitting the candies above, but we need to reserve k so that the conditions are not equal to 0. Thus, the result will be ((n - k) + k - 1) C (k - 1), which simplifies ( n - 1) C (k - 1). ((N - k) due to the fact that we set aside k for each of k members).

Thus, the end result will be Sum [i = 2..n] (n - 1) C (i - 1), since the expression contains at least 2 members and at most n members. We know that Sum [i = 1..n] (n - 1) C (i - 1) = 2 ^{n - 1} therefore Sum [i = 2..n] (n - 1) C (i - 1) = 2 ^{n - 1} - 1.

Another way to approach this problem is explained in a comment by commentator @MarkDickinson. The findings are more straightforward.

Between each pair of sweets there is either a separator or not. This immediately gives 2^(n-1) possibilities. For some reason, OP excludes the only case where we have only 1 part, so we subtract 1 to get 2^(n-1) - 1 .

to make the argument harder. Since the problem allows only positive terms, we can insert only one separator between the candies, and we can insert them between the candies, and not 2 ends. Therefore, there are (n - 1) places where a separator may appear.