2 条题解

  • 0
    @ 2022-05-13 15:06:56

    #include <bits/stdc++.h>
    using namespace std ;
    bool v[ 10010] ;
    int n, a[ 21 ] ;
    void dfs( int k, int s )
    {

    v[ s ] = true ;
    if ( k >= n )
    {
    return ;
    }
    for ( int i = 0 ; i < n ; i ++ )
    {
    if ( a[ i ] != -1 ) // 每次往里面加的数有n中选择
    {
    int t = a[ i ] ;
    a[ i ] = -1 ;
    dfs( k - 1 , s + t ) ;
    a[ i ] = t ;
    }
    }
    }
    int main( )
    {
    cin >> n ;
    for (int i = 0 ; i < n ; i ++ )
    {
    cin >> a[ i ] ;
    }
    dfs( 0, 0 );
    int ans = 0 ;
    for ( int i = 1 ; i < 1010 ; i++ )
    {
    if ( v[ i ] )
    {
    ans ++ ;
    }
    }
    cout << ans ;
    return 0 ;
    }
    // 每次选一个数,加进去,则每次有k中选择,k = n , n - 1 , n - 2 ,……
    // 时间复杂度为n!,过60%的数据

  • 0
    @ 2021-11-07 16:44:42

    #include<bits/stdc++.h>
    using namespace std;
    int b[1001]={0},a[21]={0};
    int n,t=0;
    void dfs(int num,int sum)
    {
    if(num>n)
    {
    b[sum]=1;
    return ;
    }
    else
    {
    dfs(num+1,sum+a[num]);
    dfs(num+1,sum);
    }
    }
    int main()
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>a[i];
    }
    dfs(1,0);
    for(int j=1;j<=1000;j++)
    {
    if(b[j]==1)
    {
    t=t+1;
    }

    }
    cout<<t;
    }

  • 1

信息

ID
1013
难度
6
分类
(无)
标签
递交数
21
已通过
10
通过率
48%
上传者