Answer: Recurrences

Question: Subset sum: Say we have n items (where n is a power of 2), each with an integer weight between -m and m. We want to know if there is a subset whose sum is exactly k. The following divide-and-conquer code should do this:

bool*
subsetSumHelper(int *weight, int m, int n) {
    if(n == 1) {
        // base case: for a set with one element, only 0 and the
        // element's weight are possible sums
        bool *achieve = new bool[2 * m + 1];
        achieve += m;

        for(int i = -m; i <= m; i++) achieve[i] = false;
        achieve[0] = true;
        achieve[weight[0]] = true;

        return achieve;
    }

    // compute achievable sums for first and second halves
    bool *achieve_1 = subsetSumHelper(weight, m, n / 2);
    bool *achieve_2 = subsetSumHelper(weight + n / 2, m, n / 2);

    // I can only achieve the sums between -m * n and m * n, inclusive.
    // make achieve be an array so that achieve[-m * n] and
    // achieve[m * n] are both defined.
    bool *achieve = new bool[2 * m * n + 1];
    achieve += m * n;
    for(int i = -m * n; i <= m * n; i++) achieve[i] = false;

    // compute based on first and second halves; if there is a subset
    // of the first half with sum i and there is a subset of the second
    // half with sum j, then there is a subset of the entire array
    // with sum i+j
    for(int i = -m * n / 2; i <= m * n / 2; i++) {
        if(achieve_1[i]) {
            for(int j = -m * n / 2; j <= m * n / 2; j++) {
                if(achieve_2[j]) achieve[i + j] = true;
            }
        }
    }

    // delete the arrays in the called functions
    delete[] (achieve_1 - m * n / 2);
    delete[] (achieve_2 - m * n / 2);

    // return the achievable sums for my array
    return achieve;
}

bool subsetSum(int *weight, int m, int n, int k) {
    bool *achievable = new int[2 * m * n + 1];
    subsetSumHelper(achievable + m * n, weight, m, n);
    bool ret = achievable[k];
    delete[] achievable;
    return ret;
}

Answer: The recurrence is

  T(n) = 2 T(n / 2) + O(m^2 n^2)