- Forum
- General C++ Programming
- Number of ways of dividing an 'n' member
Number of ways of dividing an 'n' member team into units
A team of players consists of n(=5 to 100) players. It is required to divide this team into smaller units. However, the smallest allowed unit is of 5 players. Find the number of ways of dividing the team.
For example, if n=16, the possible divisions are:
1.16
2.11+5
3.10+6
4.9+7
5.8+8
6.6+5+5
Hence, the output is 6.
Other samples:
1. n=17, output=7
2. n=20, output=13
NOTE: equivalent divisions (like 6+5+5,5+6+5,5+5+6) will be counted once.
I did this using brute force (by making just about all possible combinations of numbers and checking if they summed up to n. lol.). Obviously, it took ages to compute(if it did at all).
Is there a DP solution possible for this? Can anyone plz give some hints on how to tackle this prob? Any help will be appreciated :)
For example, if n=16, the possible divisions are:
1.16
2.11+5
3.10+6
4.9+7
5.8+8
6.6+5+5
Hence, the output is 6.
Other samples:
1. n=17, output=7
2. n=20, output=13
NOTE: equivalent divisions (like 6+5+5,5+6+5,5+5+6) will be counted once.
I did this using brute force (by making just about all possible combinations of numbers and checking if they summed up to n. lol.). Obviously, it took ages to compute(if it did at all).
Is there a DP solution possible for this? Can anyone plz give some hints on how to tackle this prob? Any help will be appreciated :)
Maybe if you think the problem in a more general way.
How many ways you can divide the team if the smallest unit is n?
How many ways you can divide the team if the smallest unit is n?
Topic archived. No new replies allowed.