We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

My approach was to bottom-up fill an array A[i][j]. Where each cell represents the total number of ways you can select i elements from j possibiliities. The answer to the problem would be represented by the cell A[k-1][n-1].

The solution seems right, nevertheless I get a "Timeout Error" for the testcases 3 & 5. Is there a much more efficient way to solve that problem?

## Different Ways

You are viewing a single comment's thread. Return to all comments →

My approach was to bottom-up fill an array

`A[i][j]`

. Where each cell represents the total number of ways you can select`i`

elements from`j`

possibiliities. The answer to the problem would be represented by the cell`A[k-1][n-1]`

.The solution seems right, nevertheless I get a "Timeout Error" for the testcases 3 & 5. Is there a much more efficient way to solve that problem?

If you're computing the array each time it seems this solution would be on the O(T*n*m) ~ 10^9 which would explain why you ran out of time.

Alternatives:Option 1)

Precompute the array once for n = 1000. Read the results for each test case out of the array.

Option 2)

Use a recursive function with memoization (easy for this problem)