Skip to content

Instantly share code, notes, and snippets.

@andriybuday

andriybuday/SimpleKnapsack.java

Created February 8, 2020 19:43
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save andriybuday/29c85a2ee5c17a20d141906970df46e5 to your computer and use it in GitHub Desktop.
Save andriybuday/29c85a2ee5c17a20d141906970df46e5 to your computer and use it in GitHub Desktop.
Download ZIP
SimpleKnapsack
Raw
SimpleKnapsack.java
public boolean canConstructSum(int[] a, int sum) {
int n = a.length;
boolean[] dp = new boolean[sum+1];
dp[0] = true;
for(int i = 0; i < n; ++i) {
for(int s = sum - a[i]; s >= 0; --s) {
dp[s+a[i]] |= dp[s];
}
}
return dp[sum];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment