第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-924 选数

#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <limits.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define M 100007
#define ll long long
int a[30],book[30];
int n,j,s=0,sum,f=0,cnt=0;
void dfs(int step) {
	int i;
	if(s>=sum ) {
		if(s==sum) {
			cnt++;
		}
	}
	for(i=step; i<=n; i++) {
		s+=a[i];
		book[i]=1;
		dfs(i+1);
		s-=a[i];
		book[i]=0;
	}
}
int main() {
	int i;
	scanf("%d%d",&n,&sum);
	for(i=1; i<=n; i++) {
		scanf("%d",&a[i]);
	}
	dfs(1);
	printf("%d",cnt);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[30],book[30];
int n,j,s,k,f,ans=0;
void dfs(int step)
{
    int i;
    if(s>=k)
    {
        if(s==k)
        {
            if(f==0)
            {
                f=1;
            }
            if(f)
            {
            	ans++;
            }
        }
    }
    int  m;
    for(m=step; m<n; m++)
    {
        s+=a[m];
        book[m]=1;
        dfs(m+1);
        s-=a[m];
        book[m]=0;
    }
}
int main()
{
    int i;
    cin>>n>>k;
        s=0,f=0;
        memset(book,0,sizeof(book));
        for(i=0; i<n; i++)
           cin>>a[i];
        dfs(0);
        if(f==0)
		cout<<"0"; 
        else
		cout<<ans;
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
    static int x, cnt;
    static ArrayList list = new ArrayList();
    public static void main(String[] args) throws IOException {
        StreamTokenizer s = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        s.nextToken();
        int n = (int) s.nval;
        s.nextToken();
        x = (int) s.nval;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            s.nextToken();
            arr[i] = (int) s.nval;
        }
          Arrays.sort(arr);

        dfs(arr, 0, x);
       System.out.println(cnt);
    }

    /**
     * @param arr  数组
     * @param curr 当前下标
     * @param k    和为k  题目中的X
     */
    public static void dfs(int[] arr, int curr, int k) {

        if (k == 0) {//说明组成了
            /*for (int i = 0; i < list.size(); i++) {
                System.out.print((list.get(i))+(i==list.size()-1?" ":","));
            }
            System.out.println();*/
            cnt++;
            return;//选完之后要记得return
            /**
             * 不然 残留的数据会出问题
             * 比如 2 2 2 2   第二个2已结用过了，第一个2凑成功之后，输出之后，继续递归，不选第二个2，又
             * 输出了一次第1个2，这个明显是不对的。
             *
             * 也就是，我们完成一组数据，就立即退出。
             */
        }
        if (k < 0 || curr == arr.length) return;
        /**
         * 
         * 必须在这句话后面  不然会数组下标越界
         * 剪枝
         * 后面不可能再凑层k
         */
        if (arr[curr] > k) {
            return;//剪枝
        }
        //不选
        dfs(arr, curr + 1, k);
        //选
        list.add(arr[curr]);
        int idx = list.size() - 1;
        dfs(arr, curr + 1, k - arr[curr]);
        //回溯  如果程序会执行到这，说明就时没执行到底  中间一次递归的时候的值不符合题意  需要回溯  然后回到再上一步  再次递归选择
        list.remove(idx);
    }

}

n,x=map(int,input().split())
a=list(map(int,input().split()))
dp=[[1]+[0 for j in range(x)] for i in range(n+1)]
for i in range(1,n+1):
    for j in range(x+1):
        if j>=a[i-1]:
            dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i-1]]
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][x])