Last Updated: 29 Sep, 2020
Break Number
Moderate
Asked in companies
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
Approaches
- The Naive approach uses a brute-force method to generate all the possible compositions possible by partitioning the given number
- 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.
- When we place a number at a position we decrease the remaining sum and move to the next position.
- 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.
- 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]. ]
- In the end, we will print all possible combinations.
- This approach might look similar to the brute force approach in terms of time and space complexity yet, it is more efficient for some large numbers.
- We can improve the complexity by only generating unique combinations and thus by making less recursive calls in each iteration.
- The idea is to move recursively from start till the remaining sum so that the chosen number will always be a valid one.
- When we select a number we append it to the array, update the start as this new number and the remaining sum accordingly( Notice that we are always appending numbers in non-decreasing order only, which helps in reducing the overhead of duplicacy).
- Whenever the remaining sum is 0, we print the combination and return removing the last added number.
Similar problems