Let $X_i \subset \Bbb{N}$ be the total choices (naively figured) in some algorithm for succesively presented options $i=1..n$ Then naively there are $\prod_{i=1}^n |X_i|$ possible combinations of choices to check.
But what if we know something more, that for each choice vector $(x_i) \in X_1 \times \dots \times X_n$ that we actually care about, we have the bound:
$$ \sum_{i=1}^n a_i x_i \leq s $$
where $a_i, s \in \Bbb{N}$ are fixed for a given algorithm input.
Question: Can we efficiently design a decision tree with alot less combinations than the naive count? Namely, can we get a polynomial-sized decision tree with respect to $n$, that was constructed in polynomial time?
You can assume each $X_i$ is for the most part a range of whole numbers.
Also you can assume that the upper bound of $X_i$ is precisely $|X_i|$ so for simplicity of analysis, assume that $X_i = \{1, \dots, |X_i|\}$.
For fixed $a_i,s$, yes, you're bounded by $ { {\sum_{i=1}^n |X_i| } \choose s }$. I'm not sure of your motivation for doing so, perhaps you would be interested in the theory of kernelization https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-videos/lecture-18-complexity-fixed-parameter-algorithms/