Difference between revisions of "Talk:TADM2E 3.12"
| (One intermediate revision by the same user not shown) | |||
| Line 9: | Line 9: | ||
------------------------------------------------- | ------------------------------------------------- | ||
| − | The above example would work fine with the given solution, the problem arises when there are multiple subsets (mutually exclusive or not) of S | + | The above example would work fine with the given solution, the problem arises when there are multiple subsets (mutually exclusive or not) of S which add to k. Consider the following example: |
S = { 1, 2, 3, 4 } , k = 5 | 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. | 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. | ||
| + | |||
| + | If there are multiple subsets of S that add to k, I'm not sure that this problem can be solved in O(n) uses of the black box. | ||
Latest revision as of 21:34, 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 which 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.
If there are multiple subsets of S that add to k, I'm not sure that this problem can be solved in O(n) uses of the black box.
