# Thread: Sum of subsets backtracking

1. ## 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?

2. 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++)

3. 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

4. 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.

5. 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;
}```

6. 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

```int coins_array[] = {1,1,2,2,3};