How to count the combinations not greater than a given volume in a knapsack problem? You are given a certain set of items with weight wi and the volume of the bag. 

Case:

Input: 

3 (count of items) 10 (volume of the bag)
1 2 4 (weight for each item)

Output

8 (since you can put any item in or not 2 * 2 *2)


I have a naive solution using DFS as


public class Main {
    public static void main(String... args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int volume = scanner.nextInt();
        int[] weights = new int[size];
        for (int i = 0; i &lt; size; ++i) weights[i] = scanner.nextInt();
        System.out.println(getCounts(weights, 0, volume));
    }

    private static int getCounts(int[] nums, int pos, int target) {
        if (target &lt; 0) return 0;
        if (pos &gt;= nums.length) return 1;
        return getCounts(nums, pos+1, target) +
            getCounts(nums, pos+1, target-nums[pos]);
    }
}


As expected, it produced TLE and I added cache to avoid re-calculation as

public class Main {
    private static int[][] cache;
    public static void main(String... args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int volume = scanner.nextInt();
        cache = new int[size+1][volume+1];
        for (int i = 0; i &lt;= size; ++i) {
            for (int j = 0; j &lt;= volume; ++j) {
                cache[i][j] = -1;
            }
        }
        int[] weights = new int[size];
        for (int i = 0; i &lt; size; ++i) weights[i] = scanner.nextInt();
        System.out.println(getCounts(weights, 0, volume));
    }

    private static int getCounts(int[] nums, int pos, int target) {
        if (target &lt; 0) return 0;
        if (pos == nums.length) return 1;
        if (cache[pos][target] != -1) return cache[pos][target];
        int count = getCounts(nums, pos+1, target) +
            getCounts(nums, pos+1, target-nums[pos]);
        cache[pos][target] = count;
        return count;
    }
}


But the OJ prompt me of memory error while the memory is within the limit => 13064K &lt; 32768K, any idea to solve this issue? 


Why did it fail? 
Could a DP solution without backtracking be found for this?


Any help will be appreciated :)

Here is the original problem in Chinese.
Why did it fail? 


Look at the code cache = new int[size+1][volume+1];. Suppose size is 1 and volume is $10^9$. One int uses 4 bytes. So this cache will use $4 \times 2 \times 10^9$ bytes, which is about 8G, which is way much bigger than the limit, 32768K. So the online judge will show you out-of-memory error.


  Could a DP solution without backtracking be found for this?


The right strategy here is called "meet in the middle". Here is the idea of the algorithm, where $w$ is the volume of the bag.


Split the items into $A$ and $B$, two lists of approximately equal size.
Compute all possible sums of items in A, appending them to array arrA. Sort arrA.
Compute all possible sums of items in A, appending them to array arrB. Sort arrB.
For each number in arrA, find the last element in arrB such that the sum of the two is not greater than $w$. Let its index be $upper$. Add $upper + 1$ to the total.
Return total.


The time-complexity of the algorithm is $O(n2^{n/2})$, which comes from sorting two arrays of size about $2^{n/2}$. For $n= 30$, we get $30\times 2^{30/2}=30\times32768$, which is about 1 million. 

The space-complexity of the algorithm is $O(2^{n/2})$. For example, if $n= 30$, we allocate two arrays of longs of size $2^{15}$, which spans $2\times2^{15}\times8$ bytes, which is less than 600K. We need some extra work memory for sorting and etc, which will at most triple the memory allocated specifically for our algorithm. 

Here is the implementation in Java.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        final int n = sc.nextInt();
        final int w = sc.nextInt();
        final long[] v = new long[n];
        for (int i = 0; i &lt; n; ++i) v[i] = sc.nextLong();

        int total;
        if (n == 1) {
            if (v[0] &lt;= w) total = 2;
            else total = 1;
        } else {
            final int half_n = n / 2;

            final long[] front = getSortedSums(v, 0, half_n);
            final long[] behind = getSortedSums(v, half_n, n);

            int lastIndexFront = front.length - 1;
            while (front[lastIndexFront] &gt; w) lastIndexFront--;

            int upper = behind.length - 1;
            for (int i = 0; i &lt;= lastIndexFront; i++) {
                while (front[i] + behind[upper] &gt; w) upper--;
                total += upper + 1;
            }
        }

        System.out.println(total);
    }

    // Return all possible sums of elements in the specified segment of v,
    // sorted. Note the first sum is 0, representing the empty sum.
    private static long[] getSortedSums(long[] v, final int low, final int high) {
        int index = 0;
        final long[] sums = new long[1 &lt;&lt; (high - low)];
        for (int i = low; i &lt; high; i++) {
            long u = v[i];
            int end = 1 &lt;&lt; (i - low);
            for (int j = 0; j &lt; end; j++) {
                sums[++index] = sums[j] + u;
            }
        }
        Arrays.sort(sums);
        return sums;
    }
}