N Sum Pattern

Pattern for $N$-sum, where $N \geq 2$. (For 1-sum, The straightforward solution is to scan the whole array and find the targets.)

Hash Table

• Build a hash map for $\lfloor N/2 \rfloor$ tuples
  • Key is sum of $\lfloor N/2 \rfloor$ elements
  • Value is the array containing all $\lfloor N/2 \rfloor$ tuples
• Iterate the possibilities of left $N - \lfloor N/2 \rfloor$ tuples
  • Find thier complement tuples in the hash map whose key = target - sum(this tuple)
  • Use a (hash-)set to store the valid tuples to avoid duplicates
• Transfer the tuples in the set to an array and return it

Pseudo Code

$\begin{aligned} & NSum ([x_0, x_1, ... , x_{N-1}], target): \\ & \quad \text{// 1. Build a hash map for } \lfloor N/2 \rfloor \text{ tuples} \\ & \quad \text{Initialize } HashMap \\ & \quad \text{for } i_0 \in [0, N - 1]: \\ & \quad \quad \text{for } i_1 \in [i_0 + 1, N - 1]: \\ & \quad \quad \quad ... \\ & \quad \quad \quad \text{for } i_{\lfloor N/2 \rfloor - 1} \in [i_{\lfloor N/2 \rfloor - 2} + 1, N - 1]: \\ & \quad \quad \quad \quad sum = x_{i_0} + x_{i_1} + ... + x_{i_{\lfloor N/2 \rfloor - 1}} \\ & \quad \quad \quad \quad tuple = [ x_{i_0} , x_{i_1} , ... , x_{i_{\lfloor N/2 \rfloor - 1}} ] \\ & \quad \quad \quad \quad HashMap \gets (sum, tuple) \\ & \quad \text{// 2. Iterate the possibilities of left } N - \lfloor N/2 \rfloor \text{ tuples} \\ & \quad \text{Initialize } Sets \\ & \quad \text{for } i_0 \in [0, N - 1]: \\ & \quad \quad \text{for } i_1 \in [i_0 + 1, N - 1]: \\ & \quad \quad \quad ... \\ & \quad \quad \quad \text{for } i_{N - \lfloor N/2 \rfloor - 1} \in [i_{N - \lfloor N/2 \rfloor - 2} + 1, N - 1]: \\ & \quad \quad \quad \quad sum = x_{i_0} + x_{i_1} + ... + x_{i_{N - \lfloor N/2 \rfloor - 1}} \\ & \quad \quad \quad \quad tuple = [ x_{i_0} , x_{i_1} , ... , x_{i_{N - \lfloor N/2 \rfloor - 1}} ] \\ & \quad \quad \quad \quad complement = target - sum \\ & \quad \quad \quad \quad \text{if } complement \text{ in } HashMap \\ & \quad \quad \quad \quad \text{and } tuple \text{ doesn't overlap the } HashMap(complement): \\ & \quad \quad \quad \quad \quad \text{ Add } set(tuple, HashMap(complement)) \text{ to } Sets \\ & \quad \text{// 3. Transfer the tuples in } Sets \text{ to an array} \\ & \quad \text{Initialize } Array \\ & \quad \text{for } set \text { in } Sets: \\ & \quad \quad \text{ Add } set \text{ to } Array \\ & \quad \text{ return } Array & \quad \end{aligned}$

Two Pointers

vector<vector<int>> nSum(vector<int>& nums, int N, int target) {
  vector<vector<int>> tuples;
  if (nums.size() && N >= 2) {
    sort(nums.begin(), nums.end());
    nSum(nums, N, target, 0, tuples, {});
  }
  return tuples;
}

void nSum(vector<int>& sorted, int N, int target, int start,
          vector<vector<int>>& tuples, vector<int> prefix) {
  assert(sorted.size());
  assert(start >= 0);
  assert(sorted[start] <= sorted.back());

  // Stop if N is smaller than 2 or
  // left elements are less than N elements.
  if (N < 2 || sorted.size() - start < N) {
    return;
  }

  int min = sorted[start];
  int max = sorted.back();

  // Stop if target is too small or too large.
  if (target < N * min || target > N * max) {
    return;
  }

  // Find tuples after N is reduced to 2.
  if (N == 2) {
    twoSum(sorted, target, start, tuples, prefix);
    return;
  }

  // Loop element in range [start, sorted.size() - (N - 1))
  for (int i = start ; i < sorted.size() - N + 1 ; ++i) {
    int current = sorted[i];

    // Skip the duplicates.
    if (i > start && current == sorted[i - 1]) {
      continue;
    }

    // Skip if it's too small.
    if (current + (N - 1) * max < target) {
      continue;
    }

    // Stop looping after it becomes too large.
    if (N * current >= target) {
      if (N * current == target && sorted[i + N - 1] == current) {
        vector<int> padding(N, current);
        vector<int> tuple(prefix);
        tuple.insert(tuple.end(), padding.begin(), padding.end());
        tuples.push_back(tuple);
      }
      break;
    }

    // Find N-1 Sum.
    int nextTarget = target - current;
    vector<int> nextPrefix(prefix);
    nextPrefix.push_back(current);
    nSum(sorted, N - 1, nextTarget, i + 1, tuples, nextPrefix);
  }
}

void twoSum(vector<int>& sorted, int target, int start,
            vector<vector<int>>& tuples, vector<int> prefix)
{
  assert(sorted.size());
  assert(start >= 0);
  assert(sorted[start] <= sorted.back());

  // Stop if number of left elements are less than two.
  if (sorted.size() -  start < 2) {
    return;
  }

  int min = sorted[start];
  int max = sorted.back();

  // Stop if target is too small or too large.
  if (target < 2 * min || target > 2 * max) {
    return;
  }

  int left = start;
  int right = sorted.size() - 1;
  while (left < right) {
    int sum = sorted[left] + sorted[right];

    if (sum == target) {
      vector<int> tuple(prefix);
      tuple.push_back(sorted[left]);
      tuple.push_back(sorted[right]);
      tuples.push_back(tuple);
      ++left;
      --right;

      // Skip the duplicate left values.
      while (left < right && sorted[left] == sorted[left - 1]) {
        ++left;
      }

      // Skip the duplicate right values.
      while (left < right && sorted[right] == sorted[right + 1]) {
        --right;
      }

      continue;
    }

    sum < target ? ++left : --right;
  }
}