Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Break Number

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
14 upvotes
Asked in companies
Deutsche BankAppleTata Consultancy Services (TCS)

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. 
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= N <= 50

Time Limit: 1sec
Sample Input 1:
4
Sample Output 1:
4
1 1 1 1 
1 1 2
2 2
1 3
Explanation For Sample Input 1:
Here notice that all combinations are sorted in non-decreasing order and [1, 1, 2] and [1, 2, 1] are the same and printed as [1, 1, 2]. 

Note: 1 1 1 1
      2 2
      4 
      1 3
      1 1 2  is also a valid output as the order of different sequences doesn’t matter.
Sample Input 2:
1
Sample Output 2:
1
Full screen
Console