Thread: Sum of subsets backtracking

I'm trying to implement a version of subset sum using backtracking. From an array of coins, I want to obtain a certain sum. this is my code so far but I'm getting no output:

Code:

#include <stdio.h>
#define MAX 1024

int coins_array[] = {1,1,1,1,1,3,3,3,3,3,3,3,3,3,3,10,10,10,10,10,15,15,15,15,15,15};
int N = sizeof(coins_array) / sizeof(coins_array[0]);
int S = 27, x[MAX];




void back(int step)
{
    int Sol[100], total = 0;
    for (int v = 0; v < N; v++)
    {
        Sol[step] = coins_array[v];
        total += Sol[step];


        for(int i = 0; i < step; i++)
        {
            if(Sol[i]+v <= S)
            {
                if(total == S)
                {
                    printf("%d:\n", S);
                    printf("%d ", Sol[i]);
                }
                else
            back(step+1);
            }
        }
        total -= coins_array[v];
    }
}




int main()
{
    back(0);
    return 0;
}

Any ideas?

The variable 'step' has the value 0 since that's what you initially passed to the back function. The condition of the second for loop in the back function is 'i < step' but both 'i' and 'step' equal 0 so that block won't be executed.

So change this

for(int i = 0; i < step; i++)

to this

for(int i = 0; i <= step; i++)

I'm getting a segmentation fault now, this is what my debugger says:
Program received signal SIGSEGV, Segmentation fault.
0x0000555555555178 in back (step=<error reading variable: Cannot access memory at address 0x7fffff7feefc>) at coinsV5.c:11
11 {
(gdb) where
#0 0x0000555555555178 in back (step=<error reading variable: Cannot access memory at address 0x7fffff7feefc>) at coinsV5.c:11
#1 0x000055555555526c in back (step=0) at coinsV5.c:28

Originally Posted by Salem

A couple of thoughts spring to mind.

2. You're processing garbage data
> Sol[step] = coins_array[v];
...
> if(Sol[i]+v <= S)
On the recursion, you have a fresh uninitialised Sol array, of which you initialise only one element.
But you go onto try and use 0..step of them.

Could you please explain this a bit more? Why is it garbage data, shouldn't I be processing the data from the array of coins to check each value? I made some progress with the code, but getting an infinite loop atm:

Code:

#include <stdio.h>


#define MAX 1024


int coins_array[] = {1,1,1,1,1,3,3,3,3,3,3,3,3,3,3,10,10,10,10,10,15,15,15,15,15,15};
int N = sizeof(coins_array) / sizeof(coins_array[0]);
int S = 27, Sol[MAX], sum, sol;


int acceptable(int step)
{
    int i = 0, sum = 0;
    for(i = 1; i <= step; i++)
    {
        sum += Sol[i];
    }
    if((sum <= S) && (step <= N))
        return 1;
    return 0;
}


int solution(int sum)
{
    if (sum == S)
        return 1;
    return 0;
}


void print_solution(int step)
{
    int i;
    for(i = 1 ; i <= step ; ++i)
        printf("%d ",Sol[i]);


    printf("\n");
}


void back(int step)
{
    int i;
    for(i = 0; i < N; i++)
    {
        Sol[step] = coins_array[i];
        sum += coins_array[i];


        if(acceptable(step) == 1)
        {
            if(solution(sum) == 1)
            {
                print_solution(step);
            }
            else
                back(step+1);
        }
        sum -= coins_array[i];


    }
}


int main()
{
    back(1);
    return 0;
}

UPDATE: I've updated the code again, I'm getting output that adds to the target sum. Still have 2 problems: it uses a value more times than it appears in the original and it doesn't print all unique solutions

Code:

#include <stdio.h>


#define MAX 1024


int coins_array[] = {1,1,1,1,1,3,3,3,3,3,3,3,3,3,3,10,10,10,10,10,15,15,15,15,15,15};
int N = sizeof(coins_array) / sizeof(coins_array[0]);
int S = 27, Sol[MAX], IndexUsed[MAX], total;




int acceptable(int step)
{
    int i = 0, sum = 0;
    for(i = 1; i <= step; i++)
    {
        sum += Sol[i];
    }
    if((sum <= S) && (step <= N))
        return 1;
	else
    	return 0;
}


int solution(int sum)
{
    if (sum == S)
        return 1;
    return 0;
}


void print_solution(int step)
{
    int i;
    for(i = 1 ; i <= step ; ++i)
        //printf("%d (%d) ",Sol[i], IndexUsed[i]);
		printf("%d ", Sol[i]);
    printf("\n");
}


void back(int step)
{
    int i;
    for(i = IndexUsed[step]+1; i < N; i++)
    {
        Sol[step] = coins_array[i];
        IndexUsed[step] = i; 
        total += coins_array[i];


        if(acceptable(step) == 1)
        {
            if(solution(total) == 1)
            {
                print_solution(step);
            }
            else
                back(step+1);
        }
        total -= coins_array[i];
    }
}


int main()
{
    back(1);
    return 0;
}

Output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
1 1 1 1 1 1 1 1 1 1 1 1 15
1 1 1 1 1 1 1 1 1 1 1 1 15
1 1 1 1 1 1 1 1 1 1 1 1 15
1 1 1 1 1 1 1 1 1 1 1 1 15
1 1 1 1 1 1 1 1 1 1 1 1 15
1 1 1 1 1 1 1 1 1 1 1 1 15