Supposedly I have an array of size n. Find the largest combination of numbers( o

Question

Supposedly I have an array of size n. Find the largest combination of numbers( of any size) using backtrack and recursion in C++. The numbers sum needs to be smaller than or equal to target number x.

For example, if there is an array of size 6: [1,5,2,3,8,6] and the target number is 10, the ouput should be [1,8] and [3,6], which both sum up to 9.

Another example, if there is an array of size 8:[2,6,1,0,9,2,6,7] and the target number is 11, the output would be [2,2,7], [2,9], and [2,2,6,1], which all sum up to 11.

THanks

Explanation / Answer

Considering backtracking algo

if(subset is satisfying the constraint)
print the subset
exclude the current element and consider next element
else
generate the nodes of present level along breadth of tree and
recur for next levels

#include <stdio.h>
#include <stdlib.h>

#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))

static int total_nodes;

// prints subset found
void printSubset(int A[], int size)
{
for(int i = 0; i < size; i++)
{
printf("%*d", 5, A[i]);
}

printf(" ");
}

// qsort compare function
int comparator(const void *pLhs, const void *pRhs)
{
int *lhs = (int *)pLhs;
int *rhs = (int *)pRhs;

return *lhs > *rhs;
}

// inputs
// s - set vector
// t - tuplet vector
// s_size - set size
// t_size - tuplet size so far
// sum - sum so far
// ite - nodes count
// target_sum - sum to be found
void subset_sum(int s[], int t[],
int s_size, int t_size,
int sum, int ite,
int const target_sum)
{
total_nodes++;

if( target_sum == sum )
{
// We found sum
printSubset(t, t_size);

// constraint check
if( ite + 1 < s_size && sum - s[ite] + s[ite+1] <= target_sum )
{
// Exclude previous added item and consider next candidate
subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);
}
return;
}
else
{
// constraint check
if( ite < s_size && sum + s[ite] <= target_sum )
{
// generate nodes along the breadth
for( int i = ite; i < s_size; i++ )
{
t[t_size] = s[i];

if( sum + s[i] <= target_sum )
{
// consider next level node (along depth)
subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
}
}
}
}
}

// Wrapper that prints subsets that sum to target_sum
void generateSubsets(int s[], int size, int target_sum)
{
int *tuplet_vector = (int *)malloc(size * sizeof(int));

int total = 0;

// sort the set
qsort(s, size, sizeof(int), &comparator);

for( int i = 0; i < size; i++ )
{
total += s[i];
}

if( s[0] <= target_sum && total >= target_sum )
{

subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);

}

free(tuplet_vector);
}

int main()
{
int weights[] = {15, 22, 14, 26, 32, 9, 16, 8};
int target = 53;

int size = ARRAYSIZE(weights);

generateSubsets(weights, size, target);

printf("Nodes generated %d ", total_nodes);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.