小米笔试9/19

只写出来第一道.......

import java.util.*;

public class Main {
    static boolean isSuccess=false;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 有n组
        int groupNums=in.nextInt();
        for (int i = 0; i < groupNums; i++) {
            // 箱子容量
            int N=in.nextInt();
            // 玩具数量
            int n=in.nextInt();
            // 填充物数量
            int c=in.nextInt();
            // 存储玩具
            int[] nums=new int[n];
            int sum=0;
            for (int i1 = 0; i1 < n; i1++) {
                int i2 = in.nextInt();
                sum+=i2;
                nums[i1]=i2;
            }
            if(c>=N){
                System.out.println("YES");
                continue;
            }
            if(sum<N&&sum+c>=N){
                System.out.println("YES");
                continue;
            }else if(sum+c<N){
                System.out.println("NO");
                continue;
            }
            // 接着对玩具进行排列组合,看能不能凑到{N-c, N}范围之内的,背包问题
            dfs(nums,0,N,c,0);
            if(isSuccess){
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
            // 恢复标志
            isSuccess=false;
        }
    }

    public static void dfs(int[]nums,int n,int N,int c,int curr){
        if(curr>=N-c&&curr<=N){
            isSuccess=true;
            return;
        }
        if(n>=nums.length||curr>N){
            return;
        }
        if(isSuccess){
            return;
        }
        // 选或不选
        dfs(nums,n+1,N,c,curr+nums[n]);
        if(isSuccess){
            return;
        }
        dfs(nums,n+1,N,c,curr);
    }
}