Understanding the sum of the subsets

Question

I just started learning Backtracking algorithms in college. Somehow I managed to create a program for the Subset-Sum problem. It works well, but then I found that my program does not give all possible combinations.

For example: there may be a hundred combinations of the target amount, but my program gives only 30. Here is the code. It would be very helpful if someone could indicate that my mistake.

 int tot=0;//tot is the total sum of all the numbers in the set. int prob[500], d, s[100], top = -1, n; // n = number of elements in the set. prob[i] is the array with the set. void subset() { int i=0,sum=0; //sum - being updated at every iteration and check if it matches 'd' while(i<n) { if((sum+prob[i] <= d)&&(prob[i] <= d)) { s[++top] = i; sum+=prob[i]; } if(sum == d) // d is the target sum { show(); // this function just displays the integer array 's' top = -1; // top points to the recent number added to the int array 's' i = s[top+1]; sum = 0; } i++; while(i == n && top!=-1) { sum-=prob[s[top]]; i = s[top--]+1; } } } int main() { cout<<"Enter number of elements : ";cin>>n; cout<<"Enter required sum : ";cin>>d; cout<<"Enter SET :\n"; for(int i=0;i<n;i++) { cin>>prob[i]; tot+=prob[i]; } if(d <= tot) { subset(); } return 0; } 

When I run the program:

 Enter number of elements : 7 Enter the required sum : 12 Enter SET : 4 3 2 6 8 12 21 SOLUTION 1 : 4, 2, 6 SOLUTION 2 : 12 

Although 4, 8 is also a solution, my program does not show it. It is even worse - the number of inputs is 100, or more. There will be 10,000 combinations in total, but my program shows 100.

The logic I am trying to execute is:

• Take the elements of the main SET into the subset if the sum of the subset remains less than or equal to the target sum.
• If adding a certain number to the sum of the subset does this more than the goal, he does not accept it.
• As soon as it reaches the end of the set and no answer is found, it removes the most recently taken number from the set and starts looking at the numbers in the position after the last number has been deleted. (since what I store in the array '' is the position of the selected numbers from the main SET).

Answer 1

The decisions you are about to find depend on the order of the entries in the set because of your “as long as” sentence in step 1.

If you take notes until they hit the target, after you have taken, for example. “4” and “2”, “8” will take you to the target, since until “8” “2” is in your set, you will never get a subset of “4” and “8”.

You must either add the option to skip adding an entry (or add it to one subset, but not another), or change the order of your set and review it.

Answer 2

It is possible that a solution without a stack is possible, but the usual (and, as a rule, the easiest!) Way to implement reverse tracking algorithms is recursion, for example:

 int i = 0, n; // i needs to be visible to show() int s[100]; // Considering only the subset of prob[] values whose indexes are >= start, // print all subsets that sum to total. void new_subsets(int start, int total) { if (total == 0) show(); // total == 0 means we already have a solution // Look for the next number that could fit while (start < n && prob[start] > total) { ++start; } if (start < n) { // We found a number, prob[start], that can be added without overflow. // Try including it by solving the subproblem that results. s[i++] = start; new_subsets(start + 1, total - prob[start]); i--; // Now try excluding it by solving the subproblem that results. new_subsets(start + 1, total); } } 

Then you call this from main() with new_subsets(0, d); . Recursion may be difficult to understand at the beginning, but it is important that your head is around - try to simplify tasks (for example, generate Fibonacci numbers recursively) if the above does not make any sense.

Working instead of this solution, I see that as soon as you find a solution, you destroy it and start looking for a new solution from the number to the right of the first number that was included in this solution ( top = -1; i = s[top+1]; means i = s[0] , and there is a subsequent i++; ). This will skip decisions that start on the same first day. You should just do if (sum == d) { show(); } if (sum == d) { show(); } instead, to make sure you get them.

At first, I found your inner while rather confusing, but I think it really does the right thing: once i gets to the end of the array, it deletes the last number added to the partial solution, and if that number was the last number in the array, it will be loop again to remove the second-last number from the partial solution. It can never loop more than twice, because the numbers included in the partial solution are in different positions.

Answer 3

I did not analyze the algorithm in detail, but I was struck by the fact that your algorithm does not take into account the likelihood that after one solution starts with the number X, there can be many solutions from this number.

The first improvement would be to avoid flushing your stack s and the current amount after you printed the solution.