Additive equations

题目链接:题目

这题题意为从一个数字序列中找出所有可能出现的等式。

题目思路如下：

1. 如果单纯地采用枚举法一个个找出等式，绝对会超时。
2. 故选择DFS，因为每个数字都有属于自己的等式，故借此对每个数字进行拆分，并记录所有情况，得到结果。

代码如下:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[35];
int n;
bool visit[35],flag;

void DFS(int sum,int len,int start)
{
    if(len==0)
    {
        for(int i = start; i<n && sum >= a[i];i++)
        {
               if(sum == a[i])
               {
                   flag = true;
                   for(int j = 0; j<=i; j++)
                   {
                       if(visit[j])
                       {
                               if(sum == a[j])
                                   printf("%d=%d\n",a[j],a[i]);
                               else
                                   printf("%d+",a[j]);
                               sum-=a[j];
                       }
                   }    
               }
             }
     }
     else
     {
        for(int i=start;i<n;i++)
        {
            if(sum+a[i] <= a[n-1])
            {   
                len--;
                visit[i]=true;
                sum+=a[i];
                DFS(sum,len,i+1);
                sum-=a[i];
                visit[i]=false;
                len++;
            }

        }

     }
}

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
sort(a,a+n);
memset(visit,false,sizeof(visit));                    
flag = false;
for(int i=2; i<n;i++)
        DFS(0,i,0);
if(!flag)
        printf("Can't find any equations.\n\n");
else
        printf("\n");
}

return 0;
}