sql combination

Question

I have a sql query which select the best combination of hours with the heighest weight, It uses a recursive CTE to do find all the combinations of hours as shown below

Declare @EmpClasses table(Id int identity(1,1),ClassNum int,ClassWeight int,ClassHours int)
Declare @HoursReq int;

SET @HoursReq = 20;


    INSERT INTO @EmpClasses VALUES(1001,10,10),(1002,9,5),(1003,8,4),(1004,7,3),(1005,6,2),(1006,5,2),(1007,4,1);

    --INSERT INTO @EmpClasses VALUES(1001,2,2),(1002,2,2),(1003,2,2),(1004,2,2),(1005,2,2),(1006,2,2),(1007,2,2),(1008,2,2),(1009,2,2),(1010,2,2);
    --INSERT INTO @EmpClasses VALUES(1011,2,2),(1012,2,2),(1013,2,2),(1014,2,2),(1015,2,2),(1016,2,2),(1017,2,2),(1018,2,2),(1019,2,2),(1020,2,2);
    --INSERT INTO @EmpClasses VALUES(1021,2,2),(1022,2,2),(1023,2,2),(1024,2,2),(1025,2,2),(1026,2,2),(1027,2,2),(1028,2,2),(1029,2,2),(1030,2,2);


    WITH cte (Id,comIds,Total,TotalWeight)
    AS
    (
    SELECT Id
            ,Cast(ClassNum as varchar(max)) + ','
            ,ClassHours
            ,ClassWeight
    FROM @EmpClasses
    UNION ALL
    SELECT ec.Id
            ,cte.comIds + Cast(ec.ClassNum as varchar(max)) + ','
            ,cte.Total + ec.ClassHours
            ,cte.TotalWeight + ec.ClassWeight
    FROM @EmpClasses AS ec JOIN cte ON ec.Id < cte.Id
    )
    SELECT top(1)comids,Total,TotalWeight
    FROM cte 
    Where Total = @HoursReq 
    order by TotalWeight desc

However the problems lies, when the number of rows increases to iterate. It takes a very long time. Note:- Please uncomment above lines to check for the issue

Any help regarding this will be greatly appreciated

Answer 1

The number of rows generated in cte is 2^n-1 where n is the number of records in the @EmpClasses table.

So, if you use just 7 records, you generate 127 records.

However if you use 37 records, as in your full example, it needs to generate 137.438.953.471 rows. That takes some time, even if you have a fast server.

You can verify if you change the selection at the bottom of the cte, with a simple

select * from cte