Problem C : Count the Number


From: DHUOJ, 2017060303
<a type="button" class="btn btn-default" href="/solution/submit.html?problemId=5286">Submit</a> (Out of Contest)
<center> Time Limit: 3 s </center>

Description

Given n numbers, your task is to insert '+' or '-' in front of each number to construct expressions. Note that the position of numbers can be also changed.

You can calculate a result for each expression. Please count the number of distinct results and output it.

 

Input

There are several cases.
For each test case, the first line contains an integer n (1 ≤ n ≤ 20), and the second line contains n integers a1,a2, ... ,an (-1,000,000,000 ≤ ai ≤ 1,000,000,000).

 

Output

For each test case, output one line with the number of distinct results.

 

Sample Input 

2
1 2
3
1 3 5

 

Sample Output 

4
8

题意就是给你n个数，对它们进行加减，看能得到多少种结果。dfs进行搜索，用set来维护整个结果集的无重复性。


#include<iostream>
#include<cstdio>
#include<cmath> 
#include<cstring>
#include<map> 
#include<set>
using namespace std;
 
long long a[25];
int n;
set<long long>s;
 
void dfs(int step,long long sum){  
    if(step==n){  
        s.insert(sum);
        return;       
    }     
    for(int i=0;i<2;i++){   
        dfs(step+1,sum+a[step]*pow(-1,i));  
    }
    return;     
}  
 
int main(){
    while(~scanf("%d",&n)){
        memset(a,0,sizeof(a));
        s.clear();
        for(int i=0;i<n;i++){
            scanf("%lld",&a[i]);
        }
        dfs(0,0);
        cout<<s.size()<<endl;
    }
    return 0;
}