Find minimum subset that sum to at least K | Yaozong's Blog
Given a list of n integers, write a function that outputs the minimum subset of numbers that sum to at least K.
Follow up: can you beat O(nlogn)?
Solution 1: sort and linear search O(nlogn)
https://www.quora.com/Find-the-maximum-sum-of-k-length-subset-of-a-given-set-such-that-sum-is-strictly-less-than-M
Read full article from Find minimum subset that sum to at least K | Yaozong's Blog
Given a list of n integers, write a function that outputs the minimum subset of numbers that sum to at least K.
Follow up: can you beat O(nlogn)?
Solution 1: sort and linear search O(nlogn)
vector<int> minimum_subset_sum_atleast_K(vector<int>& vec, int K)
{
if(vec.size() == 0)
return {};
sort(vec.begin(), vec.end());
int n = vec.size();
vector<int> res(1, vec.back());
int cumsum = vec.back();
for(int i = n - 2; i >= 0; --i)
{
if(vec[i] < 0 || cumsum >= K) break;
cumsum += vec[i];
res.push_back(vec[i]);
}
if(cumsum >= K)
return res;
else
return {};
}
|
Solution 2: Selection Algorithm O(n) on average
http://tristan-interview.blogspot.com/2012/03/find-minimum-set-of-numbers-that-sum-to.html
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 kth 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;
}
}
}
vector<int> quick_select(vector<int>& vec, int i, int j, int K)
{
if(i > j)
return {};
if(i == j)
return {vec[i]};
int len = j - i + 1;
int idx = rand() % len + i;
int pivot = vec[idx];
swap(vec[idx], vec[j]);
int p = i, q = j;
int left_sum = vec[idx], right_sum = 0;
while(p < q) {
if(vec[p] <= pivot) {
left_sum += vec[p];
++ p;
} else {
right_sum += vec[p];
swap(vec[p], vec[--q]);
}
}
swap(vec[q], vec[j]);
vector<int> res;
if(right_sum == K) {
if(q + 1 <= j)
res.insert(res.end(), vec.begin()+q+1, vec.begin()+j+1);
return res;
}
else if(right_sum > K) {
return quick_select(vec, q+1, j, K);
}
else {
if(q + 1 <= j)
res.insert(res.end(), vec.begin()+q+1, vec.begin()+j+1);
K = K - right_sum;
vector<int> res2 = quick_select(vec, i, q, K);
res.insert(res.end(), res2.begin(), res2.end());
return res;
}
}
vector<int> minimum_subset_sum_atleast_K(vector<int>& vec, int K)
{
if(vec.size() == 0)
return {};
vector<int> res = quick_select(vec, 0, vec.size() - 1, K);
int sum = accumulate(res.begin(), res.end(), 0);
if(sum >= K)
return res;
else
return {};
}
https://www.quora.com/Find-the-maximum-sum-of-k-length-subset-of-a-given-set-such-that-sum-is-strictly-less-than-M
Read full article from Find minimum subset that sum to at least K | Yaozong's Blog
