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

A couple of thoughts spring to mind.

1. You have no exit condition for your recursion.
You keep doing back(step+1); but there is no if(step==?) return; case to tell you that you've either reached a dead-end, or you've found the answer.

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.

Quote:

---

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

TBH, I would suggest you start with

Code:

---

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

---

It's something you can work out for yourself by hand, so you have a decent chance of checking whether the code is producing the right answer.

When you've gained some measure of confidence that your code is working as you expect, then try a slightly more complicated example.