subset

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]

Problem Given a array of characters of size N. Devise an algorithm to generate all possible permutations of given size K (K <= N).  Solution Method 1 - Append characters till the length K is reached We first list the combinations using recursive procedure by selecting or not selecting characters until K length has been formed The for each combination we permute them using another recursive procedure Time : O(N! [Read More]

Problem Write a method that returns all subsets of a set. Example If we’re given a set of integers such that S = {1, 2, 3}, how can we find all the subsets of that set? For example, given S, the set of all subsets i.e. P(S) we get are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}. Here is {} is empty set denoted by Φ. [Read More]