# Algorithm and Time Complexity for k-Sum problems

In fact, there are three different k-Sum problems:

Problem1: Given unsorted integer array $$\{a_1, a_2, ..., a_n\}$$ and a target number $$T$$, determine whether there exist at least one solution $$\{a_{i_1}, \cdots, a_{i_k}\}$$ such that $$\sum_{j = 1}^{k} a_{i_j} = T$$.

For Problem1, we only need to return one solution. For example, 3-Sum, $$\{1,1,1,1,1,0,0,2,2\}$$ and $$T=3$$, we can find at least one solution $$\{1,1,1\}$$.

Problem2: Given unsorted integer array $$\{a_1, a_2, ..., a_n\}$$ and a target number $$T$$, find all distinct k-tuples such that the sum is $$T$$.

For example, 3-Sum, $$\{1,1,1,1,1,0,0,2,2\}$$ and $$T=3$$, we need to find all two solutions $$\{1,1,1\}$$ and $$\{0,1,2\}$$.

Problem3: Given unsorted integer array $$\{a_1, a_2, ..., a_n\}$$ and a target number $$T$$, find all distinct k-tuples of indices such that total sum is $$T$$.

For example, 3-Sum, $$\{1,1,1,1\}$$ and $$T=3$$, we need to return $$4$$ solutions of triple indices: $$\{0,1,2\}$$,$$\{0,1,3\}$$,$$\{1,2,3\}$$,$$\{0,2,3\}$$.

My questions:

1. For above three different k-Sum problems, what's the best time complexity we can get so far? And what's the algorithm?

I guess problem1 is $$O(n^{\lceil k/2 \rceil})$$, problem2 is $$O(n^{k-1})$$ and problem3 is $$O(n^k)$$. Is it correct? How to prove?