考核内容：
在指定的题库中自主选择不少于 15 道算法题并完成解题，其中题目难度分配如下：
- 简单题不少于 10 道
- 中等题不少于 4 道
- 困难题不少于 1 道
解答代码
23. 不再贪心的小包（困难）
代码实现：
public class Main {private static int[] factorialCache;public static int solution(int n, int m, int s, int[] like) {// 初始化缓存数组factorialCache = new int[like[n - 1] + 1];return backtrack(0, 0, 0, n, m, s, like);}public static int backtrack(int index, int currentSum, int usedMagicSticks, int n, int m, int s, int[] like) {// 如果已经遍历完所有甜点if (index == n) {// 如果当前喜爱值之和等于预期值，返回 1 表示找到一种方案，否则返回 0return currentSum == s ? 1 : 0;}// 不使用魔法棒的情况int count = backtrack(index + 1, currentSum + like[index], usedMagicSticks, n, m, s, like);// 如果还有魔法棒可用if (usedMagicSticks < m) {// 使用魔法棒的情况int factorial = getFactorial(like[index]);// 这里是关键步骤，您需要思考如何正确地累加方案数count += backtrack(index + 1, currentSum + factorial * like[index], usedMagicSticks + 1, n, m, s, like);}return count;}public static int getFactorial(int num) {// 如果缓存中已经有值，则直接返回if (factorialCache[num] != 0) {return factorialCache[num];}// 0和1的阶乘是1if (num == 0 || num == 1) {factorialCache[num] = 1;} else {// 否则计算阶乘并缓存结果factorialCache[num] = num * getFactorial(num - 1);}return factorialCache[num];}public static void main(String[] args) {// You can add more test cases hereint[] like1 = { 1, 2, 3 };int[] like2 = { 1, 1, 1 };System.out.println(solution(3, 2, 6, like1) == 2);System.out.println(solution(3, 1, 1, like2) == 0);}
}
运行结果：
