Algorithm to find best dimensions combination

Question

I am looking for an algorithm to find the best dimension combination to accomplish a desired result.

Take the following as example:

|   A    |    B   |   C   |  y  |
|--------|--------|-------|-----|
| dog    | house1 | green | 30  |
| dog    | house1 | blue  | 15  |
| cat    | house1 | green | 20  |
| cat    | house2 | red   |  5  |
| turtle | house3 | green | 50  |

A, B, C are the measured dimensions. y is the measured result.

If I want to get all combinations of dimensions that accomplish y >= 50 so the results will be:

turtle, house3, green
turtle, any,    green
turtle, house3, any
turtle, any,    any
any,    house3, green
any,    house3, any
any,    any,    green
any,    house1, green
any,    house1, any

Maybe it's a easy problem but I was trying to figure an optimal solution in terms of O(n) and I didn't found it.

Answer 1

Back here, 8 years later to answer the question using ClickHouse:

WITH table AS (
    SELECT 'dog' AS a, 'house1' AS b, 'green' AS c, 30 AS y
    UNION ALL
    SELECT 'dog' AS a, 'house1' AS b, 'blue' AS c, 15 AS y
    UNION ALL
    SELECT 'cat' AS a, 'house1' AS b, 'green' AS c, 20 AS y
    UNION ALL
    SELECT 'cat' AS a, 'house2' AS b, 'red' AS c,  5 AS y
    UNION ALL
    SELECT 'turtle' AS a, 'house3' AS b, 'green' AS c, 50 AS y
)
SELECT a, b, c, sum(y) y FROM table GROUP BY CUBE(a, b, c)
HAVING y >= 50
FORMAT PrettyCompactMonoBlock;

┌─a──────┬─b──────┬─c─────┬───y─┐
│ turtle │ house3 │ green │  50 │
│ turtle │ house3 │       │  50 │
│ turtle │        │ green │  50 │
│ turtle │        │       │  50 │
│        │ house3 │ green │  50 │
│        │ house1 │ green │  50 │
│        │ house3 │       │  50 │
│        │ house1 │       │  65 │
│        │        │ green │ 100 │
│        │        │       │ 120 │
└────────┴────────┴───────┴─────┘