Find sum of product of all possible triplets in an array in O(n)? For example, 
If array A = { 1, 2, 3 ,4 }

possible triplets are {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4} and their products are 6, 8, 12, 24 respectively.

So final answer is 50.

I found a O(n) time code, but i can't understand how it is working. 

Initially count1 array stores the original array and all other arrays has only 0 elements.

int sum = 0;

B[n-1] = count1[n];
for(i=n-2;i&gt;=0;i--) 
    B[i] = (B[i+1] + count1[i+1]);

for(i=1;i&lt;n-1;i++) 
    C[i] = (count1[i+1] * B[i+1]);

D[n-2] = C[n-2];
for(i=n-3;i&gt;=1;i--) 
    D[i] = (D[i+1] + C[i]);

for(i=0;i&lt;n-2;i++) 
    sum = (sum + count1[i+1] * D[i+1]);




If Someone wants to know how above code works, 

read this thread : 
https://www.quora.com/How-do-I-find-the-sum-of-products-of-all-possible-k-numbers-from-an-array-of-N-numbers-k-n
The code is a bit more tricky than it needs to be to achieve $O(n)$. Let $\sigma_k=\sum_ix_i^k$ (where the $x_i$ are the numbers). Then you basically want $\frac16\sigma_1^3$, but that counts some products with repeated factors. Products with one factor repeated twice are counted with weight $\frac12$, so we have to subtract $\frac12\sigma_1\sigma_2$, and then products with a single factor cubed are counted with weight $\frac16-\frac12=-\frac13$, so we have to add $\frac13\sigma_3$, for a total of $\frac16\left(\sigma_1^3-3\sigma_1\sigma_2+2\sigma_3\right)$. In your example, $\sigma_1=10$, $\sigma_2=30$ and $\sigma_3=100$, so the result is $\frac16\left(10^3-3\cdot10\cdot30+2\cdot100\right)=50$.
In  above shared Link, he used dynamic porgramming bottom up approach that difficult to think but easy to implement here i am sharing my top down approach of dp for this concept.. 

    /*
     * To change this license header, choose License Headers in Project Properties.
     * To change this template file, choose Tools | Templates
     * and open the template in the editor.
 */
package EasyProblems;

import java.util.Arrays;
import java.util.Scanner;

/**
 *
 * @author Hemant Dhanuka
 */
public class Sum_OfProduct_Ofall_K_numbers_From_Array {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        int N = s.nextInt();
        int a[] = new int[N];
        for (int l = 0; l &lt; N; l++) {
            a[l] = s.nextInt();
        }
        int k = s.nextInt();

        long dp[][] = new long[N][k];
        for (long d[] : dp) {
            Arrays.fill(d, -1);

        }
        //System.out.println(dp[1][1]);
        long ans = sum(a.length - 1, k - 1, a, dp);
        System.out.println(ans);

    }

    static long sum(int n, int k, int a[], long dp[][]) {

        if (k == -1) {
            return 1;
        }

        if (n == -1) {
            return 0;
        }

        if (dp[n][k] != -1) {
            return dp[n][k];
        }
        //if picked
        long ans1 = ((long) a[n]) * sum(n - 1, k - 1, a, dp);

        //if not picked
        long ans2 = sum(n - 1, k, a, dp);
        dp[n][k] = ans1 + ans2;
        return ans1 + ans2;
    }
}