题解 | #数组分组#

#include <stdio.h>

typedef struct
{
    int nums[50];
    int len;
}num_g_t;

int sum_5;
int sum_3;
int left_len;
int flag = 0;

num_g_t* num_gs;


int DFS(int num[], int num_5, int num_3, int* vis, int pos)
{
    /* 当前位置之前的数据加入到 3数组 */
    for(int k = 0; k < pos; k++)
    {
        num_3 += num_gs[2].nums[k]; 
        num_gs[1].nums[num_gs[1].len++] = num_gs[2].nums[k];
    }
    int tmp_num5 = num_5;
    int tmp_num3 = num_3;
    
    /* 依次查找 不同个数 到5数组后，格子数据和大小 */
   for(int j = 0; j < num_gs[2].len; j++)
   {
       
        for(int k = 0; k < j; k++)
        {
            num_5 += num_gs[2].nums[k+pos];
            num_gs[0].nums[num_gs[0].len++] = num_gs[2].nums[k+pos];
        }
         
        for(int i = pos+j; i < num_gs[2].len; i++)
        {
           num_3 += num_gs[2].nums[i];
           num_gs[1].nums[num_gs[1].len++] = num_gs[2].nums[i];
        }
        
       /* 找到相等值，返回 */
        if(sum_5 + num_5 == sum_3 + num_3)
        {
            flag = 1;
            return 1;
        }
    
       /* 回退数据，进行下一次循环 */
       num_3 = tmp_num3;
       num_5 = tmp_num5;  
       
       for(int k = 0; k < j; k++)
       {
           num_gs[0].len--;
       }
       for(int i = pos; i < num_gs[1].len; i++)
        {
           num_gs[1].len--;
        }
   }
       
    return 0;
}

int main()
{
    int size;
    int nums[50];
    
    /* 初始化输入数据num_gs[0]为 被5整除数，num_gs[1]为 被3整除数， num_gs[0]为 不能为3或5整除数 */
    num_gs = (num_g_t*)malloc(sizeof(num_g_t) * 3);
    
    memset(num_gs , 0, sizeof(num_g_t) * 3);
    sum_5 = 0;
    sum_3 = 0;
    
    if(scanf("%d", &size) != EOF)
    {
        int tmp;
        for(int i = 0; i < size; i++)
        {
            scanf("%d", &tmp);
            if(tmp != 0)            // 0不记录到数组
            {
                if(tmp % 5 == 0)
                {
                    int len = num_gs[0].len;
                    (num_gs[0].len)++;
                    num_gs[0].nums[len] = tmp;
                    sum_5 += tmp;
                }
                else if(tmp % 3 == 0)
                {
                    num_gs[1].nums[num_gs[1].len++] = tmp;
                    sum_3 += tmp;          
                }
                else
                {
                    num_gs[2].nums[num_gs[2].len++] = tmp;
                }
            }
            
        }
        
        left_len = num_gs[2].len;
        
        if(left_len == 0)                //不能被3或5整除数组 为空，则直接比较 3,5 数组和
        {
             if(sum_3 == sum_5)
             {
                 flag = 1;
             }
        }
        else
        {
            for(int i = 0; i < left_len; i++)                //遍历num_gs[2]所有位置
            {
                if(DFS(num_gs[2].nums, 0, 0, NULL, i))
                {
                    break;
                }
            }
        }
        
        if(flag)
        {
            printf("true\n");
        }
        else
        {
            printf("false\n");
        }
        
    }
    return 0;
}