Is there a simple way to find all the solutions of $x_1 + x_2 + dots + x_k + dots + x_K = N$ when $x_k$s and $N$ are all non-negative integers?

Question

Suppose I want to find all the possible solutions for the equation below.
$$x_1 + x_2 + dots + x_k + dots + x_K = N$$
where
$$x_k in text{integer}, text{i.e.}, x_1,x_2, dots, x_k in left{0,1,2, dots, Nright} $$
Right now I have written a simple script in MATLAB which is basically an exhaustive search algorithm which tests all the possible combinations for $x_k$ and returns the set of $x_k$s result in a summation of $N$. Although this works perfectly fine with small values of $N$ and $K$, as the those parameters become larger, it would take forever to see the result and it requires a gigantic amount of RAM which is beyond the capability of PC.
Hence, I am wondering has anyone seen an algorithm or something in Matlab or anywhere which would be less complex and faster and easier to implement? Any suggestion or hint would be much appreciated.

Edit
Sorry English is not my first language, I am looking for the actual solutions. I am not asking for the total number of possible solutions.

Alt · Accepted Answer

I just wrote a small python script that performs the backtracking algorithm that I mentioned in the comments.
def get_sols(N, K, sol):
    if N == 0:
        sol = sol + [0] * (K - len(sol))
        print(sol)
    elif len(sol) == K - 1:
        sol.append(N)
        print(sol)
    else:
        sol_tmp = sol
        for j in range(N + 1):
            sol = sol_tmp + [j]
            get_sols(N - j, K, sol)
        sol = sol_tmp

Example usage:
K = 5
N = 5    
get_sols(N, K, [])

I hope this can help.
As @Randy Marsh mentioned in the comments, there might be exponential number of possible solutions, so if you want to use this code for large values of $N$ or $K$, you should include other constraints in the code that significantly filter possible solutions.

RobPratt · Answer

Several integer linear programming or constraint programming solvers will find all feasible solutions upon request, without you having to write a specialized algorithm. Gurobi and Cplex both support this functionality and have MATLAB APIs.

Answered by RobPratt on January 25, 2021

Is there a simple way to find all the solutions of $x_1 + x_2 + dots + x_k + dots + x_K = N$ when $x_k$s and $N$ are all non-negative integers?

2 Answers

Example usage:

Add your own answers!

Ask a Question