Thread: Sum of subsets backtracking

  1. #1
    Registered User
    Join Date
    Jan 2021
    Posts
    7

    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. #2
    Registered User
    Join Date
    Apr 2021
    Posts
    1
    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. #3
    Registered User
    Join Date
    Jan 2021
    Posts
    7
    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. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,541
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Jan 2021
    Posts
    7
    Quote Originally Posted by Salem View Post
    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. #6
    Registered User
    Join Date
    Jan 2021
    Posts
    7
    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

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,541
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Generating Subsets
    By Soumeit in forum C Programming
    Replies: 1
    Last Post: 12-13-2014, 06:14 AM
  2. How to print out all possible subsets using set.h?
    By mgy in forum C++ Programming
    Replies: 2
    Last Post: 05-12-2014, 11:11 AM
  3. Find all subsets with sum of x
    By mgracecar in forum C Programming
    Replies: 1
    Last Post: 10-20-2013, 02:43 PM
  4. compute the subsets of a set
    By k_w_s_t_a_s in forum C Programming
    Replies: 4
    Last Post: 06-01-2003, 05:54 PM
  5. subsets
    By scottmanc in forum C++ Programming
    Replies: 7
    Last Post: 03-11-2003, 08:22 AM

Tags for this Thread