题解 | #数组分组#

#include <stdio.h>

//sum3 sum5 target = sum/2-sum3 问剩下的数是否可以存在和为
//回溯遍历rest_num 的和 用set数组辅助
int flag;
void find_target(int rest_num[], int set[], int target, int top, int rest_sum);

int main()
{
  int n;
  while (scanf("%d", &n) != EOF)
  {
    int sum3 = 0, sum5 = 0, sum = 0;
    int num;
    int rest_num[n];
    int top = -1;

    for (int i = 0; i < n; i++)
    {
      scanf("%d", &num);
      if (num % 5 == 0)
        sum5 += num;
      else if (num % 3 == 0)
        sum3 += num;
      else
        rest_num[++top] = num;

      sum += num;
    }
    int set[top + 1];
    for (int j = 0; j <= top; j++)
    {
      set[j] = 0;
    }
    //rest_num  0-top;

    if (sum % 2 != 0)
    {
      flag = 0;
    }
    else
    {
      int target = sum / 2 - sum3;
      flag = 0;
      int rest_sum = 0;
      find_target(rest_num, set, target, top, rest_sum);
    }
    if (flag)
    {
      printf("true\n");
    }
    else
      printf("false\n");
  }

  return 0;
}

void find_target(int rest_num[], int set[], int target, int top, int rest_sum)
{
  if (rest_sum == target)
  {
    flag = 1;
    return;
  }

  for (int i = 0; i <= top; i++)
  {
    if (set[i] == 0)
    {
      set[i] = 1;
      rest_sum += rest_num[i];
      find_target(rest_num, set, target, top, rest_sum);
      if (flag)
        break;
      rest_sum -= rest_num[i];
      set[i] = 0;
    }
  }
}