【问题描述】
你有一架天平和 N个砝码，这N个砝码重量依次是W1, W2, …, Wn。
请你计算一共可以称出多少种不同的重量？注意砝码可以放在天平两边。
【输入格式】
输入的第一行包含一个整数N。
第二行包含N个整数: W1, W2, W3, … Wn。
【输出格式】
输出一个整数代表答案。
【样例输入】
3
146
【样例输出】
10
解题思路：①有第一个砝码：x1，则可测出的重量有x1；②有第二个砝码：x2，则可测出的重量有x1、x1+x2、|x1-x2|、x2（相同的仅算一次）；③有第三个砝码：x3，则可测出的重量有x1、x1+x2、|x1-x2|、x2、x1+x3、|x1-x3|、x1+x2+x3、|x1+x2-x3|…（相同的仅算一次）。基于上述分析，我们需要使用不存储相同数据的HashSet来存储结果更为方便，而对于每增加一个砝码可能产生的情况，我们可以把前一个砝码产生并存储的情况拿过来与之进行处理产生更多的情况并存储。
Java代码：
import java.util.HashSet; import java.util.Iterator; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); //使用HashSet对能够称出的重量进行存储，因为HashSet不能存储相同值正是我们需要的。 HashSet<Integer> weightCase = new HashSet<>(); //将第一个砝码值直接存进去 int first = scanner.nextInt(); weightCase.add(first); //从第二个砝码开始 while (n > 1){ int x = scanner.nextInt(); //借助一个临时HashSet存储该砝码加入时与前面的砝码配合可能产生的情况 HashSet<Integer> temp = new HashSet<>(); //遍历weightCase Iterator<Integer> iterator = weightCase.iterator(); while (iterator.hasNext()){ int t = iterator.next(); temp.add(t + x); temp.add(Math.abs(t - x)); } //将添加该砝码之后可得的重量情况存储进去 weightCase.addAll(temp); weightCase.add(x); n--; } //除去重量为0这种情况 weightCase.remove(0); System.out.println(weightCase.size()); } }
import java.util.HashSet; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); HashSet<Integer> set = new HashSet<>(); int n = scanner.nextInt(); set.add(scanner.nextInt()); for (int i = 1; i < n; i++) { int fama = scanner.nextInt(); HashSet<Integer> temp = new HashSet<>(); for (Integer item : set) { temp.add(item + fama); temp.add(Math.abs(item - fama)); } temp.add(fama); set.addAll(temp); } set.remove(0); System.out.println(set.size()); } }
