In this post, I will giving two detailed implementations of Trie. One using vectors, and another using pointers.

Prerequisites:

Given an array of N integers and an integer T, find all possible combinations of indices i, j, k, l such that i < j < k < l and S[i] + S[j] + S[k] + S[l] is equal to T where S is the array of integers

Constraints: N <= 5000, T <= 10^6