题解 | #称砝码#

递归最后一个用例超时，只能for循环遍历 for 循环遍历

import java.util.Scanner;
import java.util.Stack;
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static Set<Integer> set = new HashSet<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int count = in.nextInt();
            int[] wight = new int[count]; 
            for (int i = 0; i < count; i++) {
                wight[i] = in.nextInt();
            }
            int[] num = new int[count];
            for (int i = 0; i < count; i++) {
                num[i] = in.nextInt();
            }
            set.add(0);
            dfs(wight, num);
            System.out.println(set.size());
        }
    }
    public static void dfs(int[] lengthArray, int[] num) {
        for (int i = 0; i < lengthArray.length; i++) {
            List<Integer> list = new ArrayList<>(set);
            for (int j = 0; j <= num[i]; j++) {
                for (int k = 0; k < list.size(); k++) {
                    set.add(list.get(k) + j * lengthArray[i]);
                }   
            }
        }
    }
    
}

递归的方法

import java.util.Scanner;
import java.util.Stack;
import java.util.Set;
import java.util.HashSet;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static Set<Integer> set = new HashSet<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int count = in.nextInt();
            int[] wight = new int[count]; 
            for (int i = 0; i < count; i++) {
                wight[i] = in.nextInt();
            }
            int[] num = new int[count];
            for (int i = 0; i < count; i++) {
                num[i] = in.nextInt();
            }
            dfs(wight, num, 0, 0);
            System.out.println(set.size());
        }
    }
    public static void dfs(int[] lengthArray, int[] num, int index, int sum) {
        if (index == lengthArray.length) {
            set.add(sum);
            return;
        } 
        for(int i = 0; i <= num[index]; i++) {
             dfs(lengthArray, num, index + 1, sum + i * lengthArray[index]);
        }
    }
}