Find arrays with distinct subarray sums
C (gcc), s = 19

This is basically a port of my Node.js answer. It goes one step further with the default compiler options and two steps further with -O2 or -O3.



#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;stdint.h&gt;

void search(uint8_t * arr, int n, uint8_t * sum, int * max, char * str, int depth) {
  int i, j, k, s;
  char tmp[16];

  // do we have a better array?
  if(depth &gt; *max) {
    for(str[0] = '\0', i = 0; i &lt; depth; i++) {
      sprintf(tmp, "%d ", arr[i]);
      strcat(str, tmp);
    }
    *max = depth;
  }

  // try to append i = 1 to n to the current array
  for(i = 1; i &lt;= n; i++) {
    // provided that doing so does not produce a sum that was already encountered
    if(!sum[i]) {
      for(sum[s = i] = 1, j = depth; j &amp;&amp; !sum[s += arr[j - 1]]; j--) {
        sum[s] = 1;
      }
      if(!j) {
        // this is valid: set the value in arr[] and do a recursive call
        arr[depth] = i;
        search(arr, n, sum, max, str, depth + 1);
      }
      // whether the recursive call was processed or not, we have to clear the flags
      // that have been set above
      for(sum[s = i] = 0, k = depth - 1; k &gt;= j; k--) {
        sum[s += arr[k]] = 0;
      }
    }
  }
}

int solve(int n, char * str) {
  int     max = 0;              // best length so far
  int     hi = n * (n + 1) / 2; // highest possible sum for n
  uint8_t sum[hi + 1];          // encountered sums
  uint8_t arr[n];               // array

  memset(sum, 0, (hi + 1) * sizeof(uint8_t));
  search(arr, n, sum, &amp;max, str, 0);

  return max;
}

/////////////////////////////////////////////////////////////////////////////////////

void main() {
  char str[128];
  int  n, res;

  for(n = 1; n &lt;= 19; n++) {
    res = solve(n, str);
    printf("N = %d --&gt; %d with [ %s]\n", n, res, str);
  }
}


Try it online!