Amazon Interview Question Software Engineer / Developers
Team: Risk Assessment
Country: India
Interview Type: In-Person
Obviously you have provided 0(2^n ) solution, I was asked to solve using n^2 and I can use dynamic programming
As far as I know, subset sum problem is NP-complete and therefore cannot be solved in polynomial time.
@Ravi: the example above has O(n*2^n) complexity to be more precise. Solving it in O(n^2) time complexity seems impossible to me since the number of all subsets of specific set is 2^n (where n is a size of the set). So in theory you cannot go below O(n^2) if you need to generate/print them (count them might be different case though).
This code work only for n.length <= 31, there's also no handling of sum integer overflow and it prints the same subset multiple times if there are duplicates in n array. Slightly improved (but probably slightly slower too) version:
public static void printSubSets(int nums[], int k){
Set<Integer> set = new HashSet<Integer>();
for (int num : nums) {
set.add(num);
}
for (BigInteger bi = BigInteger.ONE;
bi.bitLength() <= set.size();
bi = bi.add(BigInteger.ONE)) {
int sum = 0;
int i = 0;
Set<Integer> subset = new HashSet<Integer>();
for (int num : set) {
if (bi.testBit(i++)) {
subset.add(num);
if (sum < k) {
sum += num;
}
}
}
if (sum >= k) {
System.out.println(subset);
}
}
}
This can be improved by using Gray code for subsets generation - since two successive values in Gray code differ in only one bit we can easily reuse subset from previous iteration step (and simply add or remove one number in it). Still - printing generated subset is O(m) (where m in a length of generated subset, which is ~0.5n in average), so the overall algorithm worst case time complexity stays at O(n * n^2).
Generation of sets in descending sum order would improve best case performance, but wouldn't change the worst case performance.
char **issubset(int arr[],int key)
{
int sum=0;
int array[0][0];
for(i=0;i<sizeof(arr);i++)
{
for(j=0;j<sizeof(arr);j++)
{
if(arr[j]<=key)
{
array[i][j]=arr[j];
sum=array[i][j]+sum;
if(sum>=key)
{
break;
}
}
}
return (array);
}
//complexity is o(n^2)
Please let me know how bad (slow) is my solution and what is the order. Thanks!
public void SubsetFinder(int index, int[] fullSet, int[] currentSet)
{
if (index+1<fullSet.Length)
{
SubsetFinder(index+1, fullSet, currentSet);
Array.Resize(ref currentSet, currentSet.Length + 1);
currentSet[currentSet.Length - 1] = fullSet[index+1];
SubsetFinder(index+1, fullSet, currentSet);
}
else
{
int sum = sumOf(currentSet);
if (sum > threshold)
printSet(currentSet);
}
}
public int sumOf(int[] a)
{
int sum = 0;
for (int i = 0; i < a.Length; i++)
sum += a[i];
return sum;
}
public void printSet(int[] a)
{
string s = "";
for (int i = 0; i < a.Length; i++)
s = s+", "+a[i].ToString();
listBox1.Items.Add(s);
}
}
import java.util.Scanner;
public class java1 {
/**
* @antony
*/
public static void main(String[] args) {
int x;
Scanner in = new Scanner(System.in);
System.out
.println("enter the number of numbers that you have to find the result for");
x = in.nextInt();
int[] array = new int[x];
System.out
.println("enter the array of numbers that you have to find the result for");
for (int i = 0; i < x; i++)
array[i] = in.nextInt();
int k, y = 0,p=0;
System.out
.println("enter the value of k,for which the sub sets of the array which have sum >=k. ");
k = in.nextInt();
String stri = "{";
for (int d = 0; d < x; d++) {
for (int i = 0; i < x; i++) {
if ((i >= d) && ((i + d-p) < x)) {
y += array[i + d-p];
if (y >= k) {
for (int j = d; j <= (i + d-p); j++)
stri += " " + array[j] + " ";
stri += ",";
continue;
} else
continue;
}
}
y = 0;
p++;
}
stri += "}";
System.out.println(stri);
}
}
idea:
Step 1: Sort the array in an acending order
Step 2: Iterater from the end of the array, get the diff between the current elem and the sum, say sum1.
then the problem's order gets decreased by 1, it is equivalent to ask, find the subset of the array[1, n-1], which have sum >= sum1. Then integrate the results of all subproblems.
Just modified subset sum problem.
Subset sum problem is done using tree traversal maintaining visited node.
int a[] = {1, 2, 3, 4, 5};
int k=0;
int visited[100]={0};
void subset_sum(int i, int target)
{
/*if((i >= sizeof(a)/sizeof(a[0])) || i < 0 || target < 0){
return;
}*/
if((i > sizeof(a)/sizeof(a[0])) || i < 0)
return;
if(target <= 0) {
int j;
for(j=0;j<sizeof(a)/sizeof(a[0]);j++)
if(visited[j] == 1)
printf("%4d", a[j]);
printf("\n");
return;
}
visited[i] = 1;
subset_sum(i+1, target-a[i]);
visited[i] = 0;
subset_sum(i+1, target);
}
int main()
{
subset_sum(0, 5);
}
Hi aka,
I like your code but I'm afraid you are breaking out of the recursion too early when you do "return" in the "if(target <= 0)" condition. You can easily see it if you use int a[] = {5, 4, 3, 2, 1}, and k=11 for example. This snippet here works better:
private static void subset_sum(int i, int target)
{
if(target <= 0 && i==array.length) {
for(int j=0; j<array.length; j++)
if(visited[j] == 1) System.out.printf("%4d", array[j]);
System.out.printf("\n");
}
if((i >= array.length) || i < 0) return;
visited[i] = 1;
subset_sum(i+1, target-array[i]);
visited[i] = 0;
subset_sum(i+1, target);
}
assume the array is already sorted in ascending order.
vector<vector<int>> p15(int array[], int arrayLen, int sum) {
if (array != NULL) {
if (arrayLen == 1) {
if (array[0] >= sum) {
vector<int> v(1, array[0]);
vector<vector<int>> rr(1, v);
return rr;
}
vector<vector<int>> r;
return r;
} else if (arrayLen > 0) {
vector<vector<int>> r;
for (int i = arrayLen - 1; i >= 0; i--) {
int diff = sum - array[i];
vector<vector<int>> vect = p15(array, i, diff);
if (vect.size() > 0) {
for (vector<vector<int>>::iterator it = vect.begin(); it != vect.end(); it++) {
it->push_back(array[i]);
}
r.insert(r.end(), vect.begin(), vect.end());
}
if (array[i] >= sum) {
vector<int> v(1, array[i]);
vector<vector<int>> rr(1, v);
r.insert(r.end(), rr.begin(), rr.end());
}
}
return r;
}
}
vector<vector<int>> r;
return r;
}
If we were to assume that the array contains only positive numbers then there is some potential for cutting down on computation time, especially for large k. If using recursion, one would start from a set including all elements of the array, and then keep removing elements until the sum falls below k. At that point recursive branch is cut, which is what cuts down on the total number of function calls. Something like this:
static int K = 12;
static Integer [] array = { 1, 2, 3, 4, 5 };
static HashSet<String> resultsSet = new HashSet<String>();
private static void GenerateSubsets(ArrayList<Integer> list, int curSum) {
if(curSum < K) return; // We fell below K for the sum of all the elements in this list - return
resultsSet.add(list.toString());
for(int i=0; i < list.size(); i++) {
int curElem = list.get(i);
list.remove(i);
GenerateSubsets(list, curSum - curElem);
list.add(i, curElem);
}
}
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(array));
int overallSum = 0;
for(int i: array) overallSum += i;
GenerateSubsets(list, overallSum);
}
import java.util.HashSet;
public class PrintSubset {
public static void main(String[] args)
{
Integer arr[] = {1,2,3,4,5};
int k = 7;
allSubsets(arr,k);
}
public static void allSubsets(Integer arr[], int k)
{
int sum = 0;
HashSet<Integer> set = new HashSet();
int j = 0;int m=0;
boolean done = false;
for(int i = 0;i< arr.length ; i++)
{
m=i;
done =true;
while(done && m <arr.length){
sum += arr[m];
set.add(arr[m]);
m++;
if((sum-k)>=0)
{
System.out.println(set);
j=m;
while(j < arr.length)
{
sum += arr[j];
set.add(arr[j]);
j++;
System.out.println(set);
}
set.clear();
sum = 0;
j=0;
done = false;
m=0;
}
}
}
}
public PrintSubset() {
super();
}
}
//The results are stored in retVv. curV is the set of selected numbers.
void getSubSets(const vector<int> nums, vector<vector<int>> &retVv, vector<int> curV, int index, int remain)
{
if(index >= nums.size())
{
if(remain <=0)
retVv.push_back(curV);
return;
}
//in this case, remain will not be <=0 when index>=nums.size()
if(remain > 0 && nums[index] < 0)
return;
getSubSets(nums, retVv,curV, index+1, remain);
curV.push_back(nums[index]);
getSubSets(nums, retVv,curV,index+1, remain-nums[index]);
}
bool comp(const int &a ,const int &b)
{
return a>=b;
}
vector<vector<int>> findAllSubsetsLargetThanK(const vector<int>&nums, int target)
{
//elements in nums are sorted in descending order.
sort(nums.begin(), nums.end(), comp);
vector<vector<int>> retVv;
vector<int> curV;
getSubSets(retVv,curV,0,target);
return retVv;
}
- srdjan August 09, 2013public void printSubSets(int n[], int k){ HashSet<Integer> set = new HashSet<>(); int mask = (1 << n.length); for (int i = 1; i < mask; i++){ int sum = 0; for (int j = 0; j < n.length; j++){ if ((i & (1 << j)) > 0){ sum+=n[j]; set.add(n[j]); } } if(sum>=k){ System.out.println(set); } set.clear(); } }