0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.