入门OJ 6247【算式等式】

分手后的思念是犯贱 2021-11-10 08:24 225阅读 0赞

# **描述** #

给你N个数字，每个数字均不相同，你可以取其中任意个数字相加，如果所得到的结果在给出的数列中也能找到，则输出这个等式

# 输入输出格式 #

## **输入** ##

第一行一个数字N  
　　接下来N个数字

## **输出** ##

输出你找到的等式，注意看样例的输出格式

# 输入输出样例 #

## **输入样例1** ##

6
    1 3 5 7 8 9

## **输出样例1** ##

1+7=8
    1+8=9
    3+5=8
    1+3+5=9

# **解题思路** #

这道题首先想到的就是[分支限界法][Link 1]（<--不知道的童鞋赶紧去看看）限制了深度后才让输出的数字数量从少到多。

# **题解** #

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 int n,q;
     4 int num[101];
     5 set<int> s;//方便寻找 
     6 bool flag[10001];//标记 
     7 bool qwe=false;
     8 void dfs(int sum,int pre,int dep)//总值，开始搜索的下标，深度 
     9 {
    10     if(dep==q+1)//深度超出 
    11     {
    12         if(s.count(sum))//找得到 
    13         {
    14             qwe=true;//控制格式 
    15             for(int i=1;i<=n;i++)
    16             {
    17                 if(flag[i])//有这个数就输出 
    18                 {
    19                     if(!qwe)cout<<"+"<<num[i];
    20                     else
    21                     {
    22                         cout<<num[i];
    23                         qwe=false;
    24                     }
    25                 }
    26                   
    27             }
    28             cout<<"="<<sum<<endl;
    29         }
    30         return;//注意，这这里无论找不找得到都要退出返回 
    31     }
    32     for(int i=pre;i<=n;i++)
    33     {
    34         if(!flag[i])
    35         {
    36             flag[i]=true;
    37             dfs(sum+num[i],i+1,dep+1);
    38             flag[i]=false;//取消标记，回溯操作 
    39         }
    40     }
    41 }
    42 int main()
    43 {
    44    cin>>n;
    45    for(int i=1;i<=n;i++)
    46    {
    47         cin>>num[i];
    48         s.insert(num[i]);//存入set 
    49    }
    50    for( q=2;q<n;q++)//分支限界精髓重点，循环深度搜索，注意全局变量 
    51    {
    52         dfs(0,1,1);
    53    }
    54     return 0;
    55 }

## ##

转载于:https://www.cnblogs.com/hualian/p/11152037.html

[Link 1]: https://www.cnblogs.com/hualian/p/11151956.html