- /*
- * Generate subset summing up equal to target
- *
- * Given set {11, 9, 8, 7, 5, 3, 2, 1};
- * Given TARGET 18
- * Output subsets which subject to subset sum equal target
- * Output
- * {11, 7}
- * {11, 5, 2}
- * {9, 8, 1}
- * {9, 7, 2}
- * {9, 5, 3, 1}
- * {8, 7, 3}
- * {8, 7, 2, 1}
- * {8, 5, 3, 2}
- * {7, 5, 3, 2, 1}
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <memory.h>
- #define END_OF_ARRAY(idx, lenth_of_array) (idx)==((lenth_of_array)-1)
- #define EMPTY(stack,top) ((top)==0)
- #define PRINT_STK(arr, stack,top) do{printf("{");\\
- for(int j = 0; j<top; ++j) {\\
- printf("%d, ", arr[stack[j]]); }}while(0);
- #define PUSH_STK(stack,v, top) do{stack[*(top)]=v; ++*(top);}while(0);
- int continuous_pop_out(int stack[], // in
- int *_top); // out
- /*
- * Return the sum of the stack,
- * Only invoke after continuous_pop_out()
- */
- int cal_sum(int stack[], // in
- int arr[], // in
- int top) // in
- {
- int ret = 0;
- for( int i=0; i<top; ++i) {
- ret += arr[stack[i]];
- }
- return ret;
- }
- void gen_subset(int a[], // in, full set, should be a descending positive array
- int len, // in, size of the set
- int target) // in
- {
- int *stack = (int*)malloc(sizeof(int)*(len+1)); // store index of the array
- memset(stack, 0x0, sizeof(int)* len);
- int _top = 0; // top of stack
- int _sum =0;
- int sum_temp = 0;
- int hit_cnt = 0; // hit count
- for( int i=0; i<len; ++i) {
- sum_temp += a[i];
- if( sum_temp>target ) {
- sum_temp = _sum; // restore
- }
- else if( sum_temp==target ){
- PRINT_STK(a, stack, _top);
- printf("%d, }\\n", a[i]);
- ++hit_cnt;
- sum_temp = _sum; // restore
- }
- else { // sum_temp < target
- _sum = sum_temp;
- PUSH_STK(stack, i, &_top);
- }
- if( END_OF_ARRAY(i, len) ) {
- PUSH_STK(stack, i, &_top);
- i = continuous_pop_out(stack, &_top);
- if (i==-1) {
- break;
- }
- _sum = cal_sum(stack, a, _top);
- sum_temp = _sum;
- }
- }
- printf("There exists %d subset fulfil target %d\\n", hit_cnt, target);
- free(stack);
- }
- /*
- * Continous pop out,
- * pop out the continous part backwards, besides of this,
- * also pop out the first incontinous element, and return the larger
- * neibougher of it.
- *
- * stack_before = {1, 4, 5, 6}, _top = 4, after continous pop out
- * stack_after = {}, _top = 0, return 2,
- *
- * stack_before = {1, 4, 6, 7}, _top = 4, after continous pop out
- * stack_after = {1}, _top = 1, return 5,
- *
- * stack_before = {1, 3}, _top = 2, after continous pop out
- * stack_after = {}, _top = 0, return 2
- *
- * stack_before = {1, 2}, _top = 2, after continous pop out
- * stack_after = {}, _top = 0, return -1
- *
- * stack_before = {5, 6}, _top = 2, after continous pop out
- * stack_after = {}, _top = 0, return -1
- *
- * stack_before = {1}, _top = 1, after continous pop out
- * stack_after = {}, _top = 0, return -1
- */
- int continuous_pop_out(int stack[], // in
- int *top ) // out
- {
- if(*top<=1) { // {} or {1}
- *top = 0;
- return -1;
- }
- int gap_gt1_found = 0; // =1 means finding gap greater than 1, say 4, 2, 1
- do {
- --*top;
- if( (stack[*top]-stack[*top-1])>1 ) {
- gap_gt1_found = 1;
- break;
- }
- } while (*top>1);
- --*top;
- if (gap_gt1_found) {
- return stack[*top];
- }
- else {
- return -1;
- }
- }
- int descending_check(int a[], int l)
- {
- for( int i=0; i<l-1; ++i) {
- if( a[i]<a[i+1] ){
- printf("ascend found in %d, %d\\n", a[i], a[i+1]);
- return 0;
- }
- }
- return 1;
- }
- void gen_subset_UT(void)
- {
- //int arr[] = {3, 2, 1,}; int TARGET = 6;
- //int arr[] = {3, 2, 1,}; int TARGET = 7;
- //int arr[] = {11, 9, 8, 7, 5, 4, 3, 2, 1,}; int TARGET = 18;
- //int arr[] = {20, 14, 9, 8, 7, 5,};int TARGET = 21;
- int l = sizeof(arr)/sizeof(arr[0]);
- if(!descending_check(arr, l)) {
- return;
- }
- gen_subset(arr, l,TARGET);
- }
- int main(void)
- {
- gen_subset_UT();
- exit(0);
- }
- //该片段来自于http://www.codesnippet.cn/detail/2711201411071.html
来源: http://www.codesnippet.cn/detail/2711201411071.html