Microsoft Interview Question
Software Engineer in TestsCountry: United States
This is a very simple approach based on dynamic programming method :
the function could be launch by calling : findNumbers(list, 0, 0, goal, "");
static void findNumbers(int[] list, int index, int current, int goal, string result)
{
if (list.Length < index || current>goal)
return;
for (int i = index; i < list.Length; i++) {
if (current + list[i] == goal) {
Console.WriteLine(result + " " + list[i].ToString());
}
else if (current + list[i] < goal) {
findNumbers(list, i + 1, current + list[i], goal, result + " " + list[i].ToString());
}
}
}
In the worst case for every number you take you have 2 paths to go, one is directly to the next number using the for loop and the other is recursive call to the next number.
Therefore the complexity of the program is (2^n)
Hi Nazzer,
What if I'm going to have the array like this {1, 1,1,1,1,1,1,1,1,1,1,2, 3, 4, 5, 6 };
Your method doesn't cover all subsets.
george
ArrayList GetSubsets(int [] Set, int size, int sum, int index)
{
ArrayList<ArrayList<int>> allSubsets;
if( index == size ){
allSubsets = new ArrayList<ArrayList<int>>();
//allSubsets .add(new ArrayList()); // Add Empty subset
return allSubsets ;
}
else {
int first = Set[index];
ArrayList otherSets = GetSubsets(Set, size, sum, index + 1);
ArrayList<ArrayList<int>> allSets = new ArrayList<ArrayList<int>>();
allsubsets = getSubsets(set, index + 1);
int item = set.get(index);
ArrayList<ArrayList<Integer>> moresubsets = new ArrayList<ArrayList<Integer>>();
for (ArrayList<Integer> subset : allsubsets) {
if( IsValidSet( new ArrayList<Integer>(subset).add(item), sum) )
{
ArrayList<Integer> newsubset = new ArrayList<Integer>();
newsubset.addAll(subset); //
newsubset.add(item);
moresubsets.add(newsubset);
}
}
allsubsets.addAll(moresubsets);
}
return allsubsets;
}
public boolean IsValidSet(ArrayList set, int sum)
{
int tempSum= 0;
foreach(int elem : set)
tempSum +=elem;
return tempSum == sum;
}
import java.util.*;
public class KNumberSubset {
private int number;
private int sum;
private LinkedList<Integer> subset;
private int[] numbers={1,2,3,4,5,6};
public KNumberSubset(int[] numbers,int number) {
// TODO Auto-generated constructor stub
this.numbers=numbers;
this.number=number;
sum=0;
subset=new LinkedList<Integer>();
}
public void findSubset(int startPoint)
{
if(sum==number)
{
System.out.println(subset+" :: "+sum);
}
else
for(int i=startPoint;i<6;i++)
{
sum=sum+numbers[i];
if(sum>10)
{
sum=sum-numbers[i];
break;
}
subset.add((int)numbers[i]);
findSubset(i+1);
sum=sum-numbers[i];
subset.removeLast();
}
}
public static void main(String args[])
{
int[] numbers={1,2,3,4,5,6};
int number=10;
Arrays.sort(numbers);
KNumberSubset ki=new KNumberSubset(numbers,number);
ki.findSubset(0);
}
}
Code is good,
but i think it will fail in following scnerio's, where number will repeated
{3,2,1,3,1,5}
@Gopal
Thanks for the comment,
even for you I/P {3,2,1,3,1,5} the above code will work, assuming that the subset may contains duplicate values
[1, 1, 2, 3, 3] :: 10
[1, 1, 3, 5] :: 10
[1, 1, 3, 5] :: 10
[2, 3, 5] :: 10
[2, 3, 5] :: 10
my suggestion is to use dp, and we can do this in O(n*k) time, where k is the target sum numer.
The basic idea is to fill a Boolean dptable of size n*(k+1), and dptable[i][j] means the first i numbers form the set have a subset that sum to j, and the recursive relation is dptable[i][j]=(dptable[i-1][j])|(dptable[i-1][j-data[i]]).
Here is the code, and the output is a little ugly, is there any suggestion to improve the output based on the boolean table?
#include<iostream>
using namespace std;
bool ** dptable;
//n is the size of data, m is the largest number in the set
void find(int * data,int n, int target)
{
if(n<1||target<0)
return;
//initialize
dptable= new bool *[n];
for(int i=0;i<n;i++)
{
dptable[i]=new bool[target +1];
dptable[i][0]=true;
}
for(int i=1;i<target+1;i++)
{
if(data[0]==i)
{
dptable[0][i]=true;
}
else
dptable[0][i]=false;
}
//fill the table row by row
for(int i=1;i<n;i++)
{
for(int j=0;j<target+1;j++)
{
dptable[i][j]=(dptable[i-1][j])|(dptable[i-1][j-data[i]]);
}
}
}
void output(int *data, int m, int target) //m is row num, fisrt call should be n-1
{
if (!dptable[m][target])
{
cout<<"cannot find such a subset"<<endl;
return;
}
if(m==0&&target!=0&&dptable[0][target])
{
cout<< "{"<<target<<"}";
return;
}
if(m==0&&target==0)
{
return;
}
int i=m;
int j=target;
if (dptable[m-1][target]) //supose 0 is not in the set(otherwise, just add it to any satisfied subset)
{
output(data, i-1,j);
}
if(target>=data[i]&&dptable[m-1][target-data[i]])
{
cout<<"{"<<data[i];
output(data, i-1,target-data[i]);
cout<<"}";
}
}
void main()
{
int data[]={1,2,3,4,5,6};
int n=6;
find(data,n, 10);
output(data, n-1,10);
}
Thanks. I have modified your code for prettier output. I have also added a check to the find function so that it doesn't access invalid entries.
#include <cstdio>
#include <vector>
using namespace std;
bool** dp;
void display(const vector<int>& v) {
for (int i = 0; i < v.size(); ++i)
printf("%d ", v[i]);
printf("\n");
}
void output(const vector<int>& a, int i, int sum, vector<int>& p) {
if (i == 0 && sum != 0 && dp[0][sum]) {
p.push_back(a[i]);
display(p);
return;
}
if (i == 0 && sum == 0) {
display(p);
return;
}
if (dp[i - 1][sum]) {
vector<int> b = p;
output(a, i - 1, sum, b);
}
if (sum >= a[i] && dp[i - 1][sum - a[i]]) {
p.push_back(a[i]);
output(a, i - 1, sum - a[i], p);
}
}
void find(const vector<int>& a, int sum) {
if (a.size() == 0 || sum < 0) return;
dp = new bool*[a.size()];
for (int i = 0; i < a.size(); ++i) {
dp[i] = new bool[sum + 1];
dp[i][0] = true;
}
for (int i = 1; i < sum + 1; ++i)
dp[0][i] = (a[0] == i) ? true : false;
for (int i = 1; i < a.size(); ++i)
for (int j = 0; j < sum + 1; ++j)
dp[i][j] = (a[i] <= j) ? dp[i - 1][j] || dp[i - 1][j - a[i]] : dp[i - 1][j];
if (!dp[a.size() - 1][sum]) {
printf("There are no subsets with sum %d\n", sum);
return;
}
vector<int> p;
output(a, a.size() - 1, sum, p);
}
int main() {
vector<int> a = {1,2,3,4,5,6};
find(a, 10);
return 0;
}
void find_subsets(int arr[], size_t sz_arr, const int sum_of_subset)
{
const unsigned int max_mask_of_subset = (int)pow((double)2, (int)sz_arr);
const unsigned int mix_mask_of_subset = 1;
unsigned int sum = 0;
std::stringstream str_stream;
for (size_t mask = mix_mask_of_subset; mask < max_mask_of_subset; ++mask)
{
for (size_t index = 0; index < sz_arr; ++index)
{
if ( (mask >> index) & 0x01 )
{
sum += arr[sz_arr - 1 - index];
str_stream << arr[sz_arr - 1 - index] << " ";
}
}
if (sum == sum_of_subset)
{
std::cout << str_stream.str() << std::endl;
}
str_stream.str("");//.clear();
sum = 0;
}
}
int main()
{
int arr[] = {1,2,3,4,5,6,7,8,9,11,12,11};
size_t sz_arr = sizeof(arr)/sizeof(arr[0]);
const unsigned int sum_of_subset = 22;
find_subsets(arr, sz_arr, sum_of_subset);
return 0;
}
public void _find(int a[], int used[], int v, int sum , int current)
{
if( current > a.length )
{
return;
}
sum += a[current];
if( sum == v )
{
System.out.println(Arrays.toString(used));
return;
}else if( sum > v)
{
return;
}
for( int i = current+1; i < a.length ; i++ )
{
if( used[i] == 0 )
{ used[i] = 1;_find(a,used,v,sum,i);used[i] = 0; }
}
}
public void findSubset(int a[], int v)
{
Arrays.sort(a);
int used[] = new int[a.length];
System.out.println(Arrays.toString(a));
for(int i=0;i<a.length;i++)
{
used[i] = 1;
_find(a,used,v,0,i);
used[i] = 0;
}
}
public class SubsetInSet
{
public static void main(String args[])
{
//int[] numbers={1,2,3,4,2,2,2,2,5,2};
//int numbers[]={1,2,3,6};
int number=10;
int numbers[]={3,2,1,3,1,5};
int sum=0,j=0;
while(j<numbers.length)
{
sum=0;
String strnum="";
for(int i=j;i<numbers.length;i++)
{
sum=sum+numbers[i];
if(sum<=10)
{
strnum+= " "+Integer.toString(numbers[i]);
if(sum==10)
{
System.out.println(strnum);
break;
}
}
if(sum>10)
{
sum=sum-numbers[i];
}
}
j++;
}
}
}
Here I am adding all those numbers from array in String whose sum equals 10 and displaying them. This is a simple code I am adding. Check this out.
public static bool sumgroup(int[] input, int sum, int start, ref List<List<int>> result)
{
bool flag = false;
for (int i = start; i < input.Length; i++)
{
if (input[i] > sum)
break;
if (input[i] == sum)
{
Console.Write(input[i]);
List<int> newmatch = new List<int>();
newmatch.Add(input[i]);
result.Add(newmatch);
flag = true;
break;
}
else
{
int countResult = result.Count;
if (sumgroup(input, sum - input[i], i + 1, ref result))
{
Console.Write(input[i]);
int count = result.Count - countResult;
for (int k = 0; k < count; k++)
{
result[result.Count -1 -k].Add(input[i]);
}
flag = true;
}
}
}
return flag;
}
sample usage
mainset=[-2,-1,2,3,4,5,6]
n=len(mainset)
subset_sum(0,n,[0]*n, 0, 4)
code in python (also prints the subsets lexicographically)
def subset_sum(mi,n,curset, cursum, target):
#calculate all possible subsets sum == target
#assumes mainset is already sorted in ascending order
global mainset
if cursum>target: #return constraint violated
return
if cursum==target: #subset found print
print map(lambda i: mainset[i], filter(lambda x: curset[x]==1,range(n)))
if mi==n: #return leaf reached
return
else: #explore more subsets
for i in range(mi,n):
curset[i]=1
cursum+=mainset[i]
subset_sum(i+1,n,curset,cursum,target)
curset[i]=0
cursum-=mainset[i]
Use the following program to generate all the subsets of {1...n} elements. Once you have a subset, then its fairly simple to perform additional logic on that subset like checking if its sum is equal to 10 or not :
/*
Generate all subsets of set {1..k}
*/
void Main()
{
Console.WriteLine("Enter value of k in set {1..k}");
int subSetSize = Convert.ToInt32(Console.ReadLine());
int[] setElements = new int[subSetSize];
Console.WriteLine("Enter the elements of subset");
for(int i = 0; i < subSetSize; i++)
{
setElements[i] = Convert.ToInt32(Console.ReadLine());
}
int[] startArray = new int[subSetSize]; //all defaults to 0
int[] lastArray = new int[subSetSize];
for(int i = 0; i < lastArray.Length ; i++)
lastArray[i] = 1;
while(!startArray.AreSequenceEqual(lastArray))
{
GetNextItem(ref startArray,subSetSize);
Console.Write("{");
for(int i = 0; i < startArray.Length; i++)
{
if(startArray[i] == 1)
{
Console.Write(setElements[i]);
Console.Write(",");
}
}
Console.WriteLine("}");
}
}
/* - Start from rightmost element. Check if the element is smaller than the upper limit or not. If smaller then
increment it by 1, followed by setting all elements further(right) to it to 1.
*/
public void GetNextItem(ref int[] start, int subSetSize)
{
int p = subSetSize - 1;
while(!(start[p] != 1))
{
p = p - 1;
}
start[p] = 1;
for(int i = p + 1; i < subSetSize; i++)
{
start[i] = 0;
}
}
// Define other methods and classes here
Here's how I would do this in Haskell:
subsetSum n ns = [ns | (t, ns) <- subsets ns, t == n]
where
subsets = foldr (\n a -> (n, [n]):map (\(t,ns) -> (t+n,n:ns)) a ++ a) []
And testing it out in GHCi:
λ> subsetSum 0 [-3, 2, 1, 5, -2, -1]
[[-3,2,1],[-3,1,5,-2,-1],[-3,5,-2],[2,1,-2,-1],[2,-2],[1,-1]]
What about a Combination algorithm a permutation algorithm will work as well but we need to get rid of duplicates
result:
- Valentino Marin March 07, 20121234
136
145
235
46