w[1] \u2026\u00a0w[4]<\/strong>. Tree diagrams can be used to design backtracking algorithms. The following tree diagram\u00a0depicts approach of generating variable sized tuple.<\/p>\nIn the above tree, a node represents function call and a branch represents candidate element. The root node contains 4 children. In\u00a0other words, root considers every element of the set as different branch. The next level\u00a0sub-trees\u00a0correspond\u00a0to the subsets that includes the parent node. The branches at each level represent tuple element to be considered. For example, if we are at level 1, tuple_vector[1] can take any value of four branches generated. If we are at level 2 of left most node,\u00a0tuple_vector[2] can take any value of three branches generated, and so on\u2026<\/p>\n
For example the left most child of root generates all those subsets that include w[1]. Similarly the second child of root generates all those subsets that includes w[2] and excludes w[1].<\/p>\n
As we go down along depth of tree we add elements so far, and if the added sum is\u00a0satisfying\u00a0explicit constraints, we will continue to generate child nodes further. Whenever the constraints are not met, we stop further generation of sub-trees\u00a0of that node, and backtrack to previous node to explore the nodes not yet explored. In many scenarios, it saves considerable\u00a0amount\u00a0of processing time.<\/p>\n[ad type=”banner”]\n
The tree should trigger a clue to implement the backtracking algorithm (try yourself). It prints all those subsets whose sum add up to given number.\u00a0We need to explore the nodes along the breadth and depth of the tree. Generating nodes along breadth is controlled by loop and nodes along the depth are generated using recursion (post order traversal). Pseudo code given below,<\/p>\n
if(subset is satisfying the constraint)\r\n print the subset\r\n exclude the current element and consider next element\r\nelse\r\n generate the nodes of present level along breadth of tree and\r\n recur for next levels<\/pre>\nFollowing is C implementation of subset sum using variable size tuple vector. Note that the following program explores all possibilities similar to exhaustive search. It is to demonstrate how backtracking can be used. See next code to verify, how we can optimize the backtracking solution.<\/p>\n
C Programming<\/strong><\/p>\n C<\/span> <\/div> #include <stdio.h>#include <stdlib.h> #define ARRAYSIZE(a) (sizeof(a))\/(sizeof(a[0])) static int total_nodes;\/\/ prints subset foundvoid printSubset(int A[], int size){ for(int i = 0; i < size; i++) { printf("%*d", 5, A[i]); } printf("\\n");} \/\/ inputs\/\/ s - set vector\/\/ t - tuplet vector\/\/ s_size - set size\/\/ t_size - tuplet size so far\/\/ sum - sum so far\/\/ ite - nodes count\/\/ target_sum - sum to be foundvoid subset_sum(int s[], int t[], int s_size, int t_size, int sum, int ite, int const target_sum){ total_nodes++; if( target_sum == sum ) { \/\/ We found subset printSubset(t, t_size); \/\/ Exclude previously added item and consider next candidate subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum); return; } else { \/\/ generate nodes along the breadth for( int i = ite; i < s_size; i++ ) { t[t_size] = s[i]; \/\/ consider next level node (along depth) subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum); } }} \/\/ Wrapper to print subsets that sum to target_sum\/\/ input is weights vector and target_sumvoid generateSubsets(int s[], int size, int target_sum){ int *tuplet_vector = (int *)malloc(size * sizeof(int)); subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum); free(tuplet_vector);} int main(){ int weights[] = {10, 7, 5, 18, 12, 20, 15}; int size = ARRAYSIZE(weights); generateSubsets(weights, size, 35); printf("Nodes generated %d\\n", total_nodes); return 0;}<\/code><\/pre> <\/div>\nThe power of backtracking appears when we combine explicit and implicit constraints, and we stop generating nodes when these checks fail. We can improve the above algorithm by strengthening the constraint checks and presorting the data. By sorting the initial array, we need not to consider rest of the array, once the sum so far is greater than target number. We can backtrack and check other possibilities.<\/p>\n
Similarly, assume the array is presorted and we found one subset. We can generate next node excluding the present node only when inclusion of next node\u00a0satisfies\u00a0the constraints. Given below is optimized implementation (it prunes the subtree if it is not satisfying contraints).<\/p>\n[ad type=”banner”]\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Backtracking Set 4 (Subset Sum) – Backtracking – Subset sum problem is to find subset of elements that are selected from a given set whose sum adds up.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,73907],"tags":[74480,74639,74629,70502,73908,74160,74492,74613,74625,74621,74636,74268,74641,74617,74637,74638,74642,74640,74620,74635,74618,70622,74622,74623,70158,74624,74630,74627,70595,74631,70593,70616,74626,74632,74615,70614,74633,74496,74619,74616,74614,74634,70574,74644,74643,74628,73910,70640,70683],"class_list":["post-25644","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-backtracking-algorithm","tag-8-queens-problem","tag-all-combinations-of-4-numbers","tag-array-sum","tag-backtrack","tag-backtracking-algorithm","tag-backtracking-algorithm-example","tag-backtracking-definition","tag-backtracking-set-4-subset-sum","tag-bit-masking","tag-bitmask","tag-branch-and-bound-method","tag-combination-of-numbers","tag-define-backtrack","tag-density-problems","tag-example-of-subset","tag-find-a-solution","tag-find-the-solution","tag-finding-solutions","tag-how-to-find-force","tag-if-sum","tag-integer-problems","tag-np-complete","tag-permutation-problems-with-solutions","tag-problem-sums","tag-rod-cutting-problem","tag-solving-integers","tag-space-tree","tag-subset-examples","tag-subset-sum","tag-subset-sum-algorithm","tag-subset-sum-problem","tag-subset-sum-problem-dynamic-programming","tag-subset-sum-problem-example","tag-subset-sum-problem-java","tag-subset-sum-problem-using-backtracking","tag-sum-of-subset-problem","tag-sum-of-subset-problem-example","tag-sum-of-subset-problem-using-backtracking","tag-sum-of-subset-problem-using-backtracking-algorithm","tag-sum-of-subset-problem-using-backtracking-example","tag-sum-of-subsets-using-backtracking","tag-sum-set","tag-sunset-time","tag-that-sums-it-up","tag-uva-100","tag-uva-database","tag-what-is-backtracking","tag-what-is-np-complete","tag-what-is-subset"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25644","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25644"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25644\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25644"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25644"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25644"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}