subset-sum.c

#include <stdio.h>

int count = 0;

void subset_sum(int k, int n, int r)  {
	if(n < 0)
		return;
	if(r == 0 && n == 0) {
		count++;
		return;
	}
	if(r == 0 && n != 0) {
		return;
	}
	
	subset_sum(k+1, n-k, r-1);
	subset_sum(k+1, n, r-1);
}

int main(void) {
	int N = 10;
	int n = 10;
	int remain = n;
	scanf("%d", &N);
	subset_sum(1, N, remain);
	printf("%d\n", count);
	return 0;
}