a C sample of subset sum problem

subssum.c

#include <stdio.h>
#include <stdlib.h>

/*
 * 部分和のうち一つを挙げる
 * numsはn個の正整数
 * sumは求めたい和
 * 部分和が存在する場合、使わないnumsの要素を0にし、使う要素の数を返す
 * 部分和が存在しない場合、0を返す
 */
int subssum(int n, int *nums, int sum) {
    int i,j, i_next, cnt;
    int *dp = calloc((n+1)*(sum+1), sizeof(int));
    /*
     * dpat(x,y) numsの先頭x個だけで、yが作れるか
     * 作れない場合、0
     * 作れる場合、その部分和のうち一番後ろにあるものの番号(これを辿って部分和を再現する)
     */
#define dpat(x,y) dp[(x)*(sum+1)+(y)]
    dpat(0,0) = ~0;
    for(i = 0; i < n; ++i) {
        for(j = 0; j <= sum; ++j) {
            /* 先頭i個でjが作れる場合 */
            if(dpat(i,j)) {
                /* 先頭i+1個でjは作れる。  */
                dpat(i+1, j) = dpat(i, j);
                if(j + nums[i] <= sum) {
                    /* 先頭i+1個でj+nums[i]は作れる。  */
                    dpat(i+1, j+nums[i]) = ~i;
                }
            }
        }
    }
    /* 部分和が存在しない */
    if(!dpat(n, sum)) {
        return 0;
    }
    /* 存在する場合、dpat(n,sum)から逆順に辿れる */
    j = sum;
    i_next = n;
    cnt = 0;
    for(i = n; i >= 0; --i) {
        if(i_next == i) {
            i_next = ~dpat(i, j);
            j -= nums[i_next];
            cnt++;
            if(j==0)break;
        } else {
            nums[i] = 0;
        }
    }
    free(dp);
    return cnt;
}

int main(int argc, char **argv)
{
    int nums[] = {1,3,7,10,13};
    int i;
    subssum(5, nums, 21);
    for(i = 0; i < 5; ++i) {
        if(nums[i]) {
            printf("%d\n", nums[i]);
        }
    }
    return 0;
}