understand

Problem Given a set of numbers [1-N] . Find the number of subsets such that the sum of numbers in the subset is a prime number. Solution  Method 1 - Using DP Maximum sum can be = N*(N+1) / 2 for any subset considered, as numbers are from 1 to N. Hence put S = (N*(N+1) / 2) in subset sum problem. For each number in the Sum S, check if there is subset of numbers from 1 to N that sum up to S - Yes that you can do with Subset Sum problem. [Read More]

DP Code Given Above Has Some Issue I Fixed It: st… PaNThErA - Dec 0, 2015DP Code Given Above Has Some Issue I Fixed It: static boolean wordBreak(String str, Set tokenMap) { int size = str.length(); if (size == 0) return true; // Create the DP table to store results of subroblems. The value wb[i] // will be true if str[0..i-1] can be segmented into dictionary words, // otherwise false. [Read More]

Problem Given a raw sentence without spaces and dictionary of words, break the raw sentence to sentence of words. String getSentence(String text, Setdictionary); // text is a string without spaces, you need to insert spaces into text, so each word seperated by the space in the resulting string exists in the dictionary, return the resulting string This problem is also known as wordbreaker problem. Example // getSentence(“iamastudentfromwaterloo”, {“from, “waterloo”, “hi”, “am”, “yes”, “i”, “a”, “student”}) -> “i am a student from waterloo” [Read More]