# Break Number

Posted: 29 Sep, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### Given a number 'N', you need to find all possible unique ways to represent this number as the sum of positive integers.

##### Note
``````1. By unique it is meant that no other composition can be expressed as a permutation of the generated composition. For eg. [1, 2, 1] and [1, 1, 2] are not unique.

2. You need to print all combinations in non-decreasing order for eg. [1, 2, 1] or [1, 1, 2] will be printed as [1, 1, 2], however, the order of printing all the sequences can be random.
``````
##### Input Format:
``````The first and the only line of the input contains an integer 'N' representing the given number.
``````
##### Output Format:
``````Each line of the output contains one unique sequence which sums up to 'N'.

There will be 'K' lines of output containing one unique sequence on each line in non-decreasing order which sums up to 'N'. 'K' is the total number of unique sequences.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= N <= 50

Time Limit: 1sec
`````` Approach 1
1. The Naive approach uses a brute-force method to generate all the possible compositions possible by partitioning the given number
2. For generating the combinations, let’s start from 1 because the minimum positive integer is 1. For every position, we will try all numbers from 1 to N, and solve the problem recursively for other positions.
3. When we place a number at a position we decrease the remaining sum and move to the next position.
4. Whenever our remaining sum = 0, we will store the sequence in an array, sort that array(to store sequence in nondecreasing order), and insert it into a set.
5. We need to store each valid combination in a set so that we can avoid the duplicate combinations in our final answer [For example, the sequence [1,2,3] and [3,1,2] are the same, so we need to sort both sequences so that they both become [1,2,3] and the set will store only one instance of [1,2,3]. ]
6. In the end, we will print all possible combinations.