Suppose I want to find an Exact Three Cover for $S$=$[1,2,3,4,5,6]$.
- Length of $S$ must total to an amount divisible by $3$.
$K$ = $length(S)/3$
It requires $K$, $3$ $element$ $sets$ to generate an Exact Three Cover for $S$. (eg. $(1,2,3)$,$(4,5,6)$)
Given all possible combinations of $3$ for $S$, I create a list called $C$.
Take note that this list is polynomial because it is fixed to $3$.
Considerations for $C$
- $(1,2,3)$ is the same as $(1,3,2)$. A sorting algorithm would address this issue for solving Exact Three Cover. (eg. Delete (1,3,2), but leave (1,2,3))
- Repeating sets can trivially be removed.(of course, leave one of the sets)
- Sets with repeating elements or sets with elements that do not exist in $S$ are deleted by a sorting algorithm.
- Because of the sorting algorithm, the worst-case input for $C$ will always have a length equal to all possible combinations of 3 from $S$ (3-element sets)
- Almost forgot, no sets with elements that total $<$ $3$ or $>$ $3$.
Question
Is there < $2^n$ combinations of $K$ to choose from a list created from all possible combinations of 3-element sets?
Edit: $n$ represents the total amount of 3-element sets of $C$. (Which is all possible combinations of 3 from $S$)