# Would this algorithm fail to count solutions \$>\$ \$1\$ for Exact-3-cover?

Decision Problem: Given a set $$S$$, is there at least a given $$N$$ $$>$$ $$1$$ amount of solutions, for an $$Exact~Cover~by~3-sets$$ for $$C%$$?

$$s$$ = $$1,2,3,4,5,6$$

$$c$$ = $$[[1,2,3],[4,3,2],[4,5,6],[5,1,6],[5,6,3]]$$

## Solutions

$$[1,2,3],[4,5,6]$$

$$[4,3,2],[5,1,6]$$

$$N$$ = $$2$$

Yes, there are $$N$$ solutions.

## Algorithm

1. Remove sets that have repeating elements

(eg. [1,1,2] is deleted from $$C$$)

2. Remove sets that have elements that don’t exist in $$S$$

(eg. [9,5,6] is deleted because $$9$$ not in $$S$$)

3. Make sure all elements in $$S$$ exist in $$C$$.

$$for$$ a $$in$$ $$range(0, length(s)):$$

$$~~~~~~~~ IF$$ $$s[a]$$ $$not$$ in $$c$$:

$$~~~~~~~~~~~~~$$OUTPUT NO

## Convert $$C$$ into a complete list

$$WHILE$$ $$c[i]$$ has [brackets]:

$$~~~~~~~~~~$$ DELETE [BRACKETS] FROM $$C$$

now $$c$$ = $$[1, 2, 3, 4, 3, 2, 4, 5, 6, 5, 1, 6, 5, 6, 3]$$

## Finally, Decide

$$n$$ = $$(‘Enter~for~N:~’))$$

$$yes$$ = $$0$$

$$for$$ a $$in$$ $$range$$(0, $$length(c)):$$

$$~~~~~~ if$$ $$c$$.count($$c$$[a]) >= $$n$$ :

$$~~~~~~~~~~ yes$$ = $$1$$

$$~~~~~~$$else:

$$~~~~~~~~~~$$OUTPUT NO

$$~~~~~~~~~~$$HALT

$$if$$ $$yes$$ == $$1$$ :

$$~~~~$$OUTPUT YES

Edit: The above should do the same below.

``yes = 0 for a in range(0, length(s)):     if c.count(s[a]) >= n:         yes = 1     else:         OUTPUT('No')         break  if yes == 1:     OUTPUT('yes') ``

## Facts to consider

1. There cannot be any sets with elements that don’t exist in $$S$$.

2. There cannot be any sets with repeating elements.

3. All elements in $$S$$ must exist in $$C$$. Else, a $$no$$ is given.
4. $$N$$ must be > $$1$$
5. If any element in $$C$$ occurs < $$N$$ times then the output must be $$No$$, because there wouldn’t be at least $$N$$ solutions.

Question

Will this algorithm always work if the input is > $$1$$, and if no how would it fail?