Untitled

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

static constexpr int32_t kTargetNumSize = 7;
static constexpr int32_t kTargetMaxSum = 20;

int64_t try_sol_count = 0;

bool check_is_valid_solution(const std::vector<int32_t> &nums) {
  try_sol_count += 1;

  int prefix_sum[kTargetNumSize];
  bool occupied[kTargetMaxSum + 1];

  memset(prefix_sum, 0, sizeof(prefix_sum));
  memset(occupied, 0, sizeof(occupied));

  for (int target_len = 1; target_len <= kTargetNumSize; target_len++) {
    for (int j = 0; j < kTargetNumSize - target_len + 1; j++) {
      prefix_sum[j] += nums[j + target_len - 1];
      if (prefix_sum[j] > 0 && prefix_sum[j] <= kTargetMaxSum) {
        occupied[prefix_sum[j]] = true;
      }
    }
  }

  for (int i = 1; i <= kTargetMaxSum; i++) {
    if (!occupied[i]) {
      return false;
    }
  }

  return true;
}

void dfs(int32_t curr_sum, std::vector<int32_t> &nums) {
  if (nums.size() == kTargetNumSize) {
    if (check_is_valid_solution(nums)) {
      cout << "valid solution found!" << endl;
      for (auto num : nums) {
        cout << num << " ";
      }

      cout << endl;
    }

    return;
  }

  for (int32_t i = -1; i < kTargetMaxSum * 4; i++) {
    if (i + curr_sum >= kTargetMaxSum) {
      break;
    }
    nums.push_back(i);
    dfs(curr_sum + i, nums);
    nums.pop_back();
  }
}

int main(int argc, char **argv) {
  std::vector<int32_t> nums;
  nums.reserve(7);
  dfs(0, nums);
  cout << "try_sol_count: " << try_sol_count;
  return 0;
}