If we have an equation with N variables of the form x1 + x2 + x3 +...+ xN with sum S, and upper and lower bounds for each of the N variables, is it possible to find the number of integer solutions (ways) to solve the problem ?

For eg :- if S=5, N=3 and the bounds for variables are 1<=X<=3, then combinations possible are (1,1,3) , (1,3,1) , (3,1,1), ( 2,2,1), (1,2,2), (2,1,2).

It's easy to find the number of ways without the bounds (upper and lower) using combinatorics. But is there any way to find the number of ways in such a case in O(S) or O(N) ?

  • 1
    $\begingroup$ If $a$ is a possible value of variable $x$, consider the subproblem without variable $x$ and sum $S-a$. $\endgroup$ – Reinstate Monica Aug 1 '18 at 14:33
  • $\begingroup$ @Solomonoff's Secret Then the time complexity would be O(m^N) where m is no of values each variable can take $\endgroup$ – Rajesh R Aug 1 '18 at 15:01
  • $\begingroup$ You would reuse solutions to identical subproblems. $\endgroup$ – Reinstate Monica Aug 1 '18 at 15:02
  • 1
    $\begingroup$ 1. Without loss of generality you can assume all the lower bounds are 0 (otherwise subtract off the lower bound from that variable and from S). 2. I suggest you study our general reference material on dynamic programming (cs.stackexchange.com/questions/tagged/dynamic-programming), apply the systematic approach outlined there, and then apply the idea explained by Solomonoff's Secret. Then you can edit your question to show what progress you've made and where you got stuck on the problem. $\endgroup$ – D.W. Aug 1 '18 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.