Finding all Chemical Reactions Given Products and Reactants
The purely combinatorial methods are a first step in modeling chemical reactions. They alone however cannot consider the possibility of the chemical reactions and the chemical stability of the reaction products.
$\ $

1.)

You can build all combinations of at least two formulas, all from the original set of given chemical formulas, and treat this as your set of given formulas. But you can also treat the whole original set of given chemical formulas.

I demonstrate the method with the first example given in the question:

$$\{ \ce{C, H2, N2, O2, CO, CO2, H2O, NH3, NO, NO2, NO3}\}$$

We set up one chemical equation with all chemical formulas that are in the given set. Let the stoichiometric factors in the chemical equation be denoted by $\nu$. Because we don't know which of the given substances will be educt and which of them will be product, we write the chemical equation without reaction arrow. Instead, a negative stoichiometric factor will later mark an educt, a positive a product:  

$$\nu_1\ce{C}+\nu_2\ce{H2}+\nu_3\ce{N2}+\nu_4\ce{O2}+\nu_5\ce{CO}+\nu_6\ce{CO2}+\nu_7\ce{H2O}+\nu_8\ce{NH3}+\nu_9\ce{NO}+\nu_{10}\ce{NO2}+\nu_{11}\ce{NO3}$$

We have to obey one of the first fundamental laws of chemistry: the Law of multiple proportions. To fulfill this law, the total sum of each chemical element in our chemical equation has to be $0$. And if ions are among our given chemical formulas, the total sum of all electric charges has to be $0$ also. But no electric charges are involved in our given example. 

We will now build a mathematical model of our chemical problem.

For each of the given chemical elements, we have to set up its balance equation from our chemical equation above:

$\ce{C}:\ \ \ \nu_1+\nu_5+\nu_6=0$
$\ce{H}:\ \ \ 2\nu_2+2\nu_7+3\nu_8=0$
$\ce{N}:\ \ \ 2\nu_3+\nu_8+\nu_9+\nu_{10}+\nu_{11}=0$
$\ce{O}:\ \ \ 2\nu_4+\nu_5+2\nu_6+\nu_7+\nu_9+2\nu_{10}+3\nu_{11}=0$

This is a linear equation system. In the general case, too, a linear equation system results. It consists of the coefficients (the numbers above) and the stoichiometric factors $\nu_i$, which are sought. In our example, the equation system has 4 equations (the number of different chemical elements and the electric charge) and 11 unknowns (the number of chemical formulas in the given set). 

Linear Algebra says how a linear equation system can be handled. We use here the matrix presentation.

Each of the 11 given chemical formulas is presented by a column vector which contains the frequency of occurence of each chemical element in the chemical formula in a prescribed order. Each of the 4 given chemical elements is presented by a row vector which contains the frequency of occurence of the chemical element in the chemical formulas in a prescribed order.

All 11 column vectors or all 4 raw vectors of the equation system are combined to give the coefficient matrix $A$. Our 11 wanted stoichiometric coefficients build the solution vector $x$, which is sought. The matrix representation of our linear equation system is than:

$$A\cdot x=\emptyset,$$ 

wherein $\emptyset$ is the zero column vector with 4 rows. It is written out:

$$\left(
\begin{array}{}
1&amp;0&amp;0&amp;0&amp;1&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0\\
0&amp;2&amp;0&amp;0&amp;0&amp;0&amp;2&amp;3&amp;0&amp;0&amp;0\\
0&amp;0&amp;2&amp;0&amp;0&amp;0&amp;0&amp;1&amp;1&amp;1&amp;1\\
0&amp;0&amp;0&amp;2&amp;1&amp;2&amp;1&amp;0&amp;1&amp;2&amp;3
\end{array}
\right)
\cdot
\left(
\begin{array}{}
\nu_1\\\nu_2\\\nu_3\\\nu_4\\\nu_5\\\nu_6\\\nu_7\\\nu_8\\\nu_9\\\nu_{10}\\\nu_{11}
\end{array}
\right)
=\left(\begin{array}{}0\\0\\0\\0\end{array}\right)$$

The solution vector $x$ can be found by solving the linear equation system by methods of Linear Algebra.

The solution vector of our example is:

$$x=\left(
\begin{array}{c}
2\nu_4+\nu_6+\nu_7+\nu_9+2\nu_{10}+3\nu_{11}\\-\nu_7+3\nu_3+\frac{3}{2}\nu_9+\frac{3}{2}\nu_{10}+\frac{3}{2}\nu_{11}\\\nu_3\\\nu_4\\-2\nu_4-2\nu_6-\nu_7-\nu_9-2\nu_{10}-3\nu_{11}\\\nu_6\\\nu_7\\-2\nu_3-\nu_9-\nu_{10}-\nu_{11}\\\nu_9\\\nu_{10}\\\nu_{11}
\end{array}
\right)$$

The different combinatorially possible chemical equations are obtained by choosing suitable values for the free variables $\nu_3,\nu_4,\nu_6,\nu_7,\nu_9,\nu_{10},\nu_{11}$.
$\ $

2.)

Further investigations could be made by searching the solutions that don't contain any other solution. That are the minimal solutions, that means the solutions that are linearly independent of the other solutions.

I found 663 chemical equations and 83 minimal solutions for the example above.

Generating only the minimal solutions in polynomial time needs particular algorithms:

Schay, G.; Pethö, Á.: Über die mathematischen Grundlagen der Stöchiometrie. Acta Chim. Acad. Sci. Hung. 32 (1962) 59-67

Pethö, Á.: Zur Theorie der Stöchiometrie Chemischer Reaktionssysteme. Wissenschaftl. Zeitschr. 6 (1964) 13-15

Pethö, Á.: Algebraic treatment of a class of chemical reactions in stoichiometry. Acta Chim. Acad. Sci. Hung. 54 (1967) 107-117

Pethö, Á.: On a class of solutions of algebraic homogeneous linear equations. Acta Math. Acad. Sci. Hung. 18 (1967) 19-23

Pethö, Á.: Kémiai reakciók egy osztályának algebrai elemzése. Magyar Kémiai Folyóirat 74 (1968) 488-491

Kumar, S.; Pethö, Á: Note on a combinatorial problem for the stoichiometry of chemical reactions. Int. Chem. Eng. 25 (1985) 767-769

Pethö, Á.: The linear relationship between stoichiometry and dimensional analysis. Chem. Eng. Technol. 13 (1990) 328-332

Szalkai, I.: Generating minimal reactions in stoichiometry using linear algebra. Hung. J. Ind. Chem. 19 (1991) 289-292
with a software code at the end of the article

Pethö, Á.: Mathematical discussion of the application of Hess‘s law. Hung. J. Ind. Chem. 21 (1993) 35-38

Pethö, Á.: Further remarks on the linear relationship between stoichiometry and dimensional analysis. Chem. Eng. Techn. Chem. Eng. Tech. 17 (1994) (1) 47-49

Pethö, Á.: Further remarks on the analogy between stoichiometry and dimensional analysis: The valuation operation. Hung. J. Ind. Chem. 23 (1995) 229-231

Laflamme, C.; Szalkai, I.: Counting simplexes in $R^n$. Hung. J. Ind. Chem. 23 (1995) 237-240

Laflamme, C.; and I. Szalkai, I.: Counting simplexes in $R^3$ Electron. J. Combin. 5 (1998) (1) #R40 11. Printed version in: J. Combin. 5 (1998) 597-607

Szalkai, I.: Handling multicomponent systems in $R^n$ I Theoretical results. J. Math. Chem. 25 (1999) 31-46

Szalkai, I.: On valuation operators in stoichiometry and in reaction syntheses. J. Math. Chem. 27 (2000) 377-386

Szalkai, I.: A new general algorithmic method in reaction syntheses using linear algebra. J. Math. Chem. 28 (2000) 1-34

Szalkai, B.; Szalkai, I.: Counting minimal reactions with specific conditions in $R^4$ J. Math. Chem. 49 (2011) 1071-1085

Szalkai, I.; Dósa, G; Tuza, Z.; Szalkai, B.: On minimal solutions of systems of linear equations with applications. Miskolc Mathematical Notes 13 (2012) (2) 529-541

Szalkai, B.; Szalkai, I.: Simplexes and their applications - A short survey. Miskolc Math. Notes 14 (2013) (1) 279-290

Szalkai, I.; Tuza, Z.: Minimum Number of Affine Simplexes of Given Dimension. Discr. Appl. Math. 180 (2015) 141-149

Szalkai, I.: Reakciómechanizmusok algoritmikus és matematikai vizsgálata (Algorithmic and Mathematical Examination of Reaction Mechanisms). PhD thesis, University of Pannonia, Veszprém, Hungary, 2014

Szalkai, I: An algorithmical and mathematical investigation of reactions. English extract of the author's PhD thesis, 2014
See the examples and references therein.

Tóth , J.: Reaction Kinetics: Exercises, Programs and Theorems. Springer, 2018
$ $

3.)

The answer above treats overall reactions. The underlying elementary reaction steps (elementary reactions) can be generated by working with the Ugi-Dugundji model: The chemical formulas are presented as graphs together with their graph matrices (Bond-Electron matrices (BE-matrices) and Reaction matrices (R-matrices)). The single elementary reaction steps will be generated successively by stepwise shifts of electrons or bonds in the set of given chemical formulas by stepwise shifting of single edges in the reaction matrix.

Ugi, I.; Gillespie, P.; Gillespie, C.: Chemistry, a finite metric topology - synthetic planning, an exercise in algebra. Trans. New York Acad. Sci. II 34 (1972) 416-432

Dugundji, J.; Ugi, I.: An algebraic model of constitutional chemistry as a basis for chemical computer programs. Top. Curr. Chem. 39 (1973) 19-64 

Dugundji, J.; Gillespie, P. D.; Marquarding, D.; Ugi, I.; Ramirez, F.: Metric spaces and graphs representing the logical structure of chemistry. in: Chemical applications of graph theory. Balaban, A. T. (Ed.), Academic Press, London 1976, 107-174

Brandt, J.; Friedrich, J.; Gasteiger, J.; Jochum, C.; Wolfgang Schubert, W.; Ugi, I.: Computer programs for the deductive solution of chemical problems on the basis of a mathematical model of chemistry. in: Wipke, W. T.; Howe, W. J.: Computer-Assisted Organic Synthesis. American Chemical Society 1977, chapter 2, 33-59 

Ugi, I.; Brandt, J.; Friedrich, J.; Gasteiger, J.; Jochum, C.; Lemmen, P.; Wolfgang Schubert, W.: The deductive solution of chemical problems by computer programs on the basis of a mathematical model of chemistry. Pure Appl. Chem. 50 (1978) 1303-1318

Ugi, I.; Brandt, J.; Friedrich, J.; Gasteiger, J.; Jochum, C.; Lemmen, P.; Schubert, W.: Computer Programs for the Deductive Solution of Chemical Problems on the Basis of a Mathematical Model of Chemistry. Pure Appl. Chem. 50 (1978) (11-12) 1303-1318

Behnke, C.; Bargon, J.: Computer-assisted topological analysis and completion of chemical reactions. J. Chem. Inf. Comput. Sci. 30 (1990) (3) 228-237 

Ugi, I; Dengler, A.: The algebraic and graph theoretical completion of truncated reaction equations. J. Math. Chem. 9 (1992) (1) 1-10