inki
BAN USERSimple recursive solution in C. It is 2^n. This will work for any targe sum value:
#include <stdio.h>
#include <stdlib.h>
void printArray(int *array, int size) {
for (int i = 0; i<size; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
void print_all_subsets(int *nums, int numsSize, int start, int sum, int *subset, int subsetSize) {
if (numsSize == 0) {
printf("Empty set");
}
if (start >= numsSize) {
return;
}
// do not include element nums[start] in the subset
print_all_subsets(nums, numsSize, start+1, sum, subset, subsetSize);
// inlcude element nums[start] in the subset
subset[subsetSize++] = nums[start];
if (nums[start] == sum) { //found a subset
printArray(subset, subsetSize);
}
print_all_subsets(nums, numsSize, start+1, sum-nums[start], subset, subsetSize);
}
int* initArray(int size) {
int *array = (int*)calloc(size, sizeof(int));
return array;
}
int main() {
int nums[]={8, 3, 5, 1, -4, -8};
int numsSize = 6;
int *subset = initArray(numsSize);
int sum = 0;
print_all_subsets(nums, numsSize, 0, sum, subset, 0);
free(subset);
}
This is just a different type of sorting question, so if you provide your own comparison function: Pi > Pj if Pi won Pj then you are all set to use any of the classic sorting algorithm. Finding the winner is equivalent to finding the max of a list of numbers which can be done in 0(n), go over player and always keep the winner of the max (winner of the two players).
And sorting can be done O(NlogN) with any of the standard sorting algorithms.
RepRussBDycus, Android test engineer at ABC TECH SUPPORT
I am working as a manager in Lionel Kiddie City company. I really enjoy my job. I like to play ...
RepPatriciaNRowe, Consultant at ADP
Hi i am a Freelance Writer and Social Media Manager who helps finance professionals and Fin-tech startups build an audience ...
RepDonnaWHale, Data Engineer at ADP
Hi, I am passionate writer with a BA in English from the Ohio State University.5+ years of experience writing ...
Repbrandysolsen, Area Sales Manager at AMD
I am a Social butterflies who enjoy travel.Have fun doing this job and project an atmosphere that reflects Amazon ...
Another solution might be to use a bloom filter per container, where each container contains that XOR of all the unique tokens in that container. Moving a luggage is just a matter of XOR the unique ID with the current container and then with the new container. Depending on the size of the containers you can choose appropriate token sizes.
- inki March 13, 2016