**Problem:**Given an array of integers, find a smallest subset (with minimum numbers of integers) that sum to at least K. For example, a[] = {2,-5,7,8,12, 4} and K = 13, then one of the minimum set can be {8, 12}.

**Solution:**One solution is first sort the array, then begin from the max integer, calculate the cumulative sum until the sum is no less than K. This solution (depending on what kind of sort algorithms you use) usually cost O(nlogn). Here we introduce a selection based algorithm which on average costs O(n) but costs O(n^2) in the worst case. The approach is similar to

*k*th order-statistics.

- Randomly choose a pivot from the current array and partition the array into two parts
*p1*and*p2*:*p1*contains integers which are smaller than the pivot;*p2*contains integers which are larger than or equal to the pivot. - Check if pivot + sum(
*p2*) == K, if so, we already find the answer; if not, then if pivot + sum(*p2*) > K but sum(*p2*) <= K, we also find the answer; if sum(*p2*) > K, we need to do further partition, but we just need to further partition*p2;*if pivot + sum(*p2*) < K, we need to do further partition, but we need to partition*p1*instead and the target value K is updated as K - pivot - sum(*p2*).

void find_min_set(int *a, int start, int end, int target) { /* generate secret number: */ int s, e, k; s = start; e = end; k = target; int sum; while(1) { srand ( time(NULL) ); int idx = ((int)rand()) % (e-s + 1) + s; /* partition and sum */ int tmp = a[idx]; a[idx] = a[e]; a[e] = tmp; sum = a[e]; int pos = s; for(int i = s; i < e; i++) { if(a[i] < a[e]) { if(pos != i) { tmp = a[pos]; a[pos] = a[i]; a[i] = tmp; } pos++; } else sum+= a[i]; } tmp = a[pos]; a[pos] = a[e]; a[e] = tmp; if(sum == k) { cout << "found " << endl; return; } else if(sum > k) { if(sum - a[pos] < k) { cout << "found " << endl; return; } s = pos + 1; sum = 0; } else { k = k - sum; sum = 0; e = pos - 1; } } }

## No comments:

## Post a Comment