Difference between revisions of "Talk:TADM2E 3.12"
(Created page with "it's kind of clear that if you should not return the minimal subset the whole set is the trivial solution. actually, the suggested solution will return the whole set any time...") |
|||
| Line 4: | Line 4: | ||
for instance: | for instance: | ||
S = {1,2,4,6,8,10}, k = 3 | S = {1,2,4,6,8,10}, k = 3 | ||
| + | |||
| + | |||
| + | |||
| + | ------------------------------------------------- | ||
| + | |||
| + | The above example would work fine with the given solution, the problem arises when there are multiple subsets (mutually exclusive or not) of S with add to k. Consider the following example: | ||
| + | |||
| + | S = { 1, 2, 3, 4 } , k = 5 | ||
| + | |||
| + | The suggested solution would use the black box on each of the subsets of S of size 3 ({ 1, 2, 3 }, { 1, 2, 4 }, { 1, 3, 4 }, { 2, 3, 4 }) and would find that each of these has a subset that sums to k = 5, thus incorrectly concluding that none of the numbers in S are required to create a subset that adds to k. | ||
Revision as of 21:32, 24 January 2019
it's kind of clear that if you should not return the minimal subset the whole set is the trivial solution. actually, the suggested solution will return the whole set any time that the first item in the given set most to be part of the subset.
for instance: S = {1,2,4,6,8,10}, k = 3
The above example would work fine with the given solution, the problem arises when there are multiple subsets (mutually exclusive or not) of S with add to k. Consider the following example:
S = { 1, 2, 3, 4 } , k = 5
The suggested solution would use the black box on each of the subsets of S of size 3 ({ 1, 2, 3 }, { 1, 2, 4 }, { 1, 3, 4 }, { 2, 3, 4 }) and would find that each of these has a subset that sums to k = 5, thus incorrectly concluding that none of the numbers in S are required to create a subset that adds to k.
