Dividing integer "n" into multiple groups where each group sum is equal to "n".

 

Let us suppose we are having a number "n" and we want to generate sequence of numbers where each sequence gives the sum is equal to "n".

Let n = 5 and intially we can write as 1 + 1 + 1 + 1 + 1 = 5.

Now there are 4  barrier(X) as shown in Figure-1 in between these "ones"where we can place our barrier. 

                             

                                                               Figure-1

What I mean by barrier is like this (11|11|1) where | represents a barrier, hence our paritition will be (2, 2, 1) for 5 or we can place our barriers like this (1|111|1) where our partition will be (1, 3, 1) or like this (111|1|1) which corresponds to another valid partition (3, 1, 1).

Hence, we can say that for each 4 positions, we can choose to place a barrier on it or not and it will always produce a unique partition. Therefore, we have 2^(5 - 1) = 2⁴ choices  (2 because we can have a barrier in between consecutive ones or not).

 Hence, if we have n ones, we'll have n - 1 barriers to place, so we'll have 2^n - 1 choices to make.

For example, n = 5

1111 | 1 = (4,1)

111 | 11 = (3,2)

11 | 111 = (2,3)

1 | 1111 = (1,4)

1 | 1 | 111 = (1,1,3)

1 | 11 | 11 = (1,2,2)

1 | 111 | 1 = (1,3,1)

11 | 1 | 11 = (2,1,2)

11 | 11 | 1 = (2,2,1)

111 | 1 | 1 = (3,1,1)

11 | 1 | 1 | 1 = (2,1,1,1)

1 | 11 | 1 | 1 = (1,2,1,1)

1 | 1 | 11 | 1 = (1,1,2,1)

1 | 1 | 1 | 11 = (1,1,1,2)

1 | 1 | 1 | 1 | 1 = (1,1,1,1,1)

11111 = (5,0)   total 16 possible combinations.

NOTE:  Each sequence above give sum equal to 5.

Hence, we generate all the possible sequences for a number which give sum equal to n.

#number_theory #bitmask #sum #integer