https://www.geeksforgeeks.org/find-sum-sum-sub-sequences/
Given an array of n integers. The task is to find the sum of sum of each of sub-sequence of the array.
Examples :
Input : arr[] = { 6, 8, 5 } Output : 76 All subsequence sum are: { 6 }, sum = 6 { 8 }, sum = 8 { 5 }, sum = 5 { 6, 8 }, sum = 14 { 6, 5 }, sum = 11 { 8, 5 }, sum = 13 { 6, 8, 5 }, sum = 19 Total sum = 76.
Method 1 (brute force):
Generate all the sub-sequence and find the sum of each sub-sequence.
Generate all the sub-sequence and find the sum of each sub-sequence.
Method 2 (efficient approach):
For an array of size n, we have 2^n sub-sequences (including empty) in total. Observe, in total 2n sub-sequences, each elements occurs 2n-1 times.
For example, arr[] = { 5, 6, 7 }
So, sum of sum of all sub-sequence will be (sum of all the elements) * 2n-1.
For an array of size n, we have 2^n sub-sequences (including empty) in total. Observe, in total 2n sub-sequences, each elements occurs 2n-1 times.
For example, arr[] = { 5, 6, 7 }
So, sum of sum of all sub-sequence will be (sum of all the elements) * 2n-1.