深度优先搜索算法

题目要求：编写一个函数，传入一个int型数组，返回该数组能否分成两组，使得两组中各元素加起来的和相等，并且，所有5的倍数必须在其中一个组中，所有3的倍数在另一个组中（不包括5的倍数），能满足以上条件，返回true；不满足时返回false。

这个题目 是考察 深度优先搜发算法的。
在需要让arr3和arr5两个数组中的和相等，就需要将other数组中的数分配到两个数组中，假设分配x到arr5中，分配y到arr3数组中，那么需要满足如下关系式。需要满足公式：
1:sum5 + x = sum3 + y
2:x + y = othersum
转换得到：
1：sum5 - sum3 = y - x
2：other = x + y
两个公式相加：sum5 - sum3 + other = 2*y
进一步可以推出：
y = (sum5 - sum3 + other)/2
sum5，sum3，other这三个数已知，可以求出y的值。也就是说，需要在other数组中找出一些数，其值为y。可以使用深度优先搜索算法进行处理。
因为数都是整数，所以对于y为浮点数的情况可以直接返回false。

#include<iostream>
#include<math.h>
using namespace std;



bool dfs(int c[], int n, bool isvisited[] ,int target)
{
    if(target == 0)
    {
        return true;
    }

    for(int i = 0; i < n; i++)
    {
        if(isvisited[i] == false)
        {
            isvisited[i] = true;
            if(dfs(c, n,isvisited, target - c[i]))
            {
                return true;
            }
            isvisited[i] = false;
        }
    }
    return false;
}

int main()
{
    int n;
    while(cin >> n)

 {
     int a[1000];
     int b[1000];
     int c[1000];
     bool isvisited[100] = {false};
     int i = 0;
     int j = 0;
     int k = 0;

     int h = 0;
     int m;
    while(h < n && cin >> m)
  {
        if(abs(m %5) == 0)
        {
            a[i++] = m;
        }
        else
            if(abs(m % 3) == 0)
           {
            b[j++] = m;
            }
            else
           {
             c[k++] = m;
           }
       h++;
   }
    int sum3 = 0, sum5 = 0, other = 0;

    for (int g = 0; g < i; g++)
    {
        sum5 += a[g];
    }

    for (int g = 0; g < j; g++)
    {
        sum3 += b[g];
    }

    for (int g = 0; g < k; g++)
    {
        other += c[g];
    }

    if((sum5 + other -sum3)% 2 != 0)
    {
        cout << "false" <<endl;
        continue;
    }

    int y = (sum5 + other -sum3) / 2;

    if(dfs(c,k,isvisited, y) == true)
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

  }
    return 0;
}

C++ 实现代码如下：

#include<iostream>
#include<math.h>
using namespace std;



bool dfs(int c[], int n, bool isvisited[] ,int target)
{
    if(target == 0)
    {
        return true;
    }

    for(int i = 0; i < n; i++)
    {
        if(isvisited[i] == false)
        {
            isvisited[i] = true;
            if(dfs(c, n,isvisited, target - c[i]))
            {
                return true;
            }
            isvisited[i] = false;
        }
    }
    return false;
}

int main()
{
    int n;
    while(cin >> n)

 {
     int a[1000];
     int b[1000];
     int c[1000];
     bool isvisited[100] = {false};
     int i = 0;
     int j = 0;
     int k = 0;

     int h = 0;
     int m;
    while(h < n && cin >> m)
  {
        if(abs(m %5) == 0)
        {
            a[i++] = m;
        }
        else
            if(abs(m % 3) == 0)
           {
            b[j++] = m;
            }
            else
           {
             c[k++] = m;
           }
       h++;
   }
    int sum3 = 0, sum5 = 0, other = 0;

    for (int g = 0; g < i; g++)
    {
        sum5 += a[g];
    }

    for (int g = 0; g < j; g++)
    {
        sum3 += b[g];
    }

    for (int g = 0; g < k; g++)
    {
        other += c[g];
    }

    if((sum5 + other -sum3)% 2 != 0)
    {
        cout << "false" <<endl;
        continue;
    }

    int y = (sum5 + other -sum3) / 2;

    if(dfs(c,k,isvisited, y) == true)
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

  }
    return 0;
}