Server-less Java : CanSum

Java as cloud-deployed AWS Lambda Functions operating through the AWS API Gateway.

Simple, interactive Java examples collected over the last 10 months or so...

Get In Touch »

Menu...

Java Prep / Deploy to AWS Function: Can Sum? {Memoised} Function: How Sum? {Memoised} Function: Decimal to Binary Conversion Function: Palindrome Check

Problem

Given a target number t, is it possible to make t as a combination sum from a list of numbers [x₁..x_n]?

Solve

Step 1. The Method

Using memoisation as a cache of already calculated values decreases the time complexity from the exponential O(2ⁿ) down to a mere linear O(n) !!

Implement