题解 | #称砝码#
称砝码
https://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c
import java.util.HashSet; import java.util.Scanner; import java.util.Set; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 int total = in.nextInt(); int[] weights = new int[total]; int[] num = new int[total]; for(int i=0; i<total;i++) { weights[i] = in.nextInt(); } for(int i=0; i<total;i++) { num[i] = in.nextInt(); } System.out.println(selectWeight(weights, num, total-1).size()); } private static Set<Integer> selectWeight(int[] weights, int[] num, int i) { Set<Integer> s = new HashSet(); if (i == 0) { for (int index = 0; index <= num[i]; index++) { s.add(weights[i] * index); } return s; } Set<Integer> prefixSet = selectWeight(weights, num, i - 1); for (int index = 0; index <= num[i]; index++) { for(Integer item: prefixSet) { s.add(weights[i] * index + item); }; } return s; } }