Question

You are given a set of integer numbers A = {a1, a2, ..., an}, where 1 ≤ ai ≤ m for all 1 ≤ i ≤ n and for a given positive integer m. Give an algorithm which determines whether you can represent a given positive integer k ≤ nm as a sum of some numbers from A, if each number from A can be used at most once. Your algorithm must have O(nk) time complexity.

Answer 1

Input :

A={a1,a2,...,an} where 1<= ai<= m and k<=n*m

Output:

Determine whether k can be represented as sum of some numbers from A(numbers can be included only once)

Solution:

Brute force approach would be to generate all subsets and check if the subset sums to the right number. The running time will be exponential i.e.,O((2^n)*k).

Optimal solution :

This problem can be solved by dynamic programming. For each element from array there are two possibilities:

1) include current element in subset and recurse for other elements with remaining sum

2) excluede cureent element and recurse for other elements

Finally, we return true if we can obtain sum by including or excluding current element else return false. Base case will be when no elements are left or k becomes negative . True is returned when k becomes 0.

Since the problem has optimal substructure and overlapping subproblems , it can be solved through dynammic programming(Memorizing recursive solutions).

Time complexity is O(N*k) where N is number of elements in array

Code:

------------------------------------------------------------------------------------------------------------------------------------

#include <bits/stdc++.h>

using namespace std;

// create a map to store solutions of subproblems

unordered_map<string, int> m;

bool check(int a[], int n, int k)

{

// return true if k becomes 0 (answer found)

if (k == 0)

return true;

// base case: no elements left or k becomes negative

if (n < 0 || k < 0)

return false;

// construct a unique map key from dynamic element of the input

string key_unique = to_string(n) + "|" + to_string(k);

// if sub-problem is seen for the first time, solve it and

// store its result in a map

if (m.find(key_unique) == m.end())

{

// Case 1. include current element in the subset (a[n]) and recurse

// for remaining elements (n - 1) with decreased k (k - arr[n])

bool inc = check(a, n - 1, k - a[n]);

// Case 2. exclude current element n from subset and recurse for

// remaining elements (n - 1)

bool exc = check(a, n - 1, k);

// assign true if we get subset by including or excluding current element

m[key_unique] = inc|| exc;

}

return m[key_unique]; //return solution if already solved

}

int main()

{

int a[] = { 10, 3, 2, 5, 8 };

int k = 17;

// number of elements

int N = sizeof(a) / sizeof(a[0]);

if (check(a, N - 1, k))

cout << "yes";

else

cout << "no";

cout<<endl;

return 0;

}

Answer 2

Program answer