杭电oj 1258 Sum It Up

dfs
要记录路径最后输出

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int sum,n,ans,x;
/*
sum和n是总和,ans用来记录是否有解,x是一个中间量,临时存数
*/
int a[15],b[15];//数组a存放输入的数据,数组b存放路径
void dfs(int nowsum,int nowk,int bi)//nowsum是当前的和,nowk记录选择的是数组a的第几个数
{								 	//bi记录数组b中的第几个数
    if(nowsum>sum) return ;//当前和超出上限,结束
    if(nowk>n) return ;//当前的数超出数组a的范围,结束
    if(nowsum==sum){//当前和等于sum,输出
        ans++;
        for(int i=0;i<bi;i++){
            if(i) cout<<'+'<<b[i];
            else cout<<b[i];
        }
        cout<<endl;
        return ;
    }
    x=a[nowk];
    b[bi]=x;
    dfs(nowsum+x,nowk+1,bi+1);//选择当前这个数
    while(a[nowk]==a[nowk+1]) nowk++;//去重
    dfs(nowsum,nowk+1,bi);//不选当前这个数
}
int main()
{
    while(cin>>sum>>n){
        if(sum==0&&n==0) return 0;
        for(int i=0;i<n;i++) cin>>a[i];
        ans=0;
        cout<<"Sums of "<<sum<<':'<<endl;
        dfs(0,0,0);
        if(ans==0) cout<<"NONE"<<endl;
    }
    return 0;
}

去重:
因为数组里有多个相同的数,我搜索的策略是选当前这个数或不选当前这个数,如果有三个2,选了第一个,之后两个2都不选 和 第一个、第三个2不选,直选第2个2 结果都是选择了一个2,但这就造成了重复,所以避免重复,在不选这个数的时候,就把后面和这个数相等的数都跳过,这就是中间那句while循环的作用。

上一篇:超声波测距实验(基于STM32F407)


下一篇:C++和java简易语法对比(OJ版)