PresentRusni.java

import java.util.HashMap;
import java.util.Map;

public class PresentRusni {

    public static void main(String[] args) {
        var scanner = new java.util.Scanner(System.in);

        var x = scanner.nextInt();
        var y = scanner.nextInt();
        var z = scanner.nextInt();
        var w = scanner.nextInt();

        var presents = backtracking(0, new int[]{x, y, z}, w);
        System.out.println(presents);
    }

    static Map<String, Integer> memo = new HashMap<>();

    private static int backtracking(int index, int[] arr, int w) {
        if (w < 0) return 0;
        if (w == 0) return 1;

        var key = index + "_" + w;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        var count = 0;
        for (int i = index; i < arr.length; i++) {
            w -= arr[i];
            count += backtracking(i, arr, w);
            w += arr[i];
        }

        memo.put(key, count);
        return count;
    }

}