Microsoft Interview Question
Country: United States
sums[s] == 1 if it's feasible to get a sum s using elements from the array a[] and 0 otherwise
parts[s] - lists the number of parts in each subset that sum up to s
for example, for 10 in the above program we have:3-element
subsets: 10 = 2+3+5 = 1 + 4 + 5 = 1 + 2 + 7
No good! Your function takes S as a parameter, as it should, but it's not used anywhere. You've effectively hard-coded the S=3 from the problem example, but S is not constant.
First, we must try and get the subsets. Let n(A) be the size of the array. Then the number of subsets of size S is n(A) C S.
Then, we must evaluate each of the subsets.
This is the simplest and right solution.
Hi below is my code let me know if anything is wrong
int a[]={1,2,5,1,6,4,9,7,0,3};
int s=3;//size of subset
int n=a.length;
int temp=0;
int expected_sum=9;
int j,i,k;
for( i=0;i<n;i++)
{temp=0;
for( j=i+1;j<(i+(s-1))&&j<n;j++)
{
temp+=a[i]+a[j];
}
for( k=j;k<n;k++)
{
expected_sum=temp+a[k];
if (expected_sum==9)
{
System.out.println("Elements are at the index"+i+--j+k);
}
}
}
This is like the 3sum problem. If integers in A are bounded, can use a bit array to represent A, then convolve with itself to find A^2, A^4 etc till A^S which can be done with O(log S) convolutions, each convolution using FFT with O(L log L) where L is the range of A. Then pick the value at N from A^S.
The idea is to use backtracking.
class Solution {
private int count = 0;
private int expect;
private int size;
private int len;
public int subsetsSum (int[] val, int expect, int size) {
this.expect = expect;
this.size = size;
this.len = vl.length - 1;
backtrack (0, 0, 0, val);
return this.count;
}
private void backtrack (int idx, int currentSize, int currentVal, int[] val) {
// If meet the end of the array
if (idx > this.len)
return;
// If find a solution
if (currentSize == this.size && currentVal == this.expect) {
count++;
return;
}
// Soltuions
// Get current value
backtrack(idx + 1, currentSize + 1, currentVal + val[idx], val);
// Do not get current value
backtrack(idx + 1, currentSize, currentVal, val);
}
}
A simple recursive function will do this,
function subArrs($arr, $sum, $size){
if($size <0)
return array();
if($size > 0 && sizeof($arr) <= $size)
if(array_sum($arr)== $sum)
return array($arr);
else
return array();
$moreSubs = subArrs(array_slice($arr, 1), $sum,$size);
$subs = subArrs(array_slice($arr, 1), $sum-$arr[0],$size - 1);
if(!$subs)
return $moreSubs;
foreach($subs as &$sub)
array_push($sub,$arr[0]);
return array_merge($subs, $moreSubs);
}
function subArrs($arr, $sum, $size){
if($size <0)
return array();
if($size > 0 && sizeof($arr) <= $size)
if(array_sum($arr)== $sum)
return array($arr);
else
return array();
$moreSubs = subArrs(array_slice($arr, 1), $sum,$size);
$subs = subArrs(array_slice($arr, 1), $sum-$arr[0],$size - 1);
if(!$subs)
return $moreSubs;
foreach($subs as &$sub)
array_push($sub,$arr[0]);
return array_merge($subs, $moreSubs);
}
def intTobinary(num):
binary = bin(num)
return binary[2:]
def subset(lst, resultSize, total):
size = len(lst)
numberOfSubsets = pow(2, size)
for count in range(0,(numberOfSubsets)):
binary = intTobinary(count)
while (len(binary) < len(lst)):
binary = '0' + binary
result = list()
for index in range(0,len(binary)):
if (binary[index] == '1'):
result.append(lst[index])
if (len(result) == resultSize and sum(result) == total):
print(result)
subset([1,2,5,3,6],3,9)
package com.gen.trials;
//subsets for the set of 1,2,3,5,6
import java.util.ArrayList;
import java.util.List;
import org.omg.CORBA.NVList;
public class Subsets {
public static void main(String[] args) {
int desiredNumberofElementsInSubset = 3;
List<List> listOfSubsets = new ArrayList<List>();
List<Integer> s = new ArrayList<Integer>();
s.add(1);
s.add(2);
s.add(5);
s.add(3);
s.add(6);
int setSize = s.size();
int numberOfSubsets = (int) (Math.pow(2, setSize));
String binaryStringOfIndex = "";
for (int i = 0; i < numberOfSubsets; i++) {
binaryStringOfIndex = Integer.toBinaryString(i);
//binary String for 0 is 0.
//but if we have 10 elements in the given list
//the binary string should also have 10 characters
//now list has four elements.
//so 0 becomes 0000, 1 becomes 0001.
//appending 4 (size of elements) - 1 (binarystring length)
int bValueSize = binaryStringOfIndex.length();
for (int k = 0; k < (setSize - bValueSize); k++) {
binaryStringOfIndex = "0" + binaryStringOfIndex;
}
//if u want subsets of size 3,
//loop should be run to only those
//binary strings with three 1's in the string
List<String> list = isRegExpressionExist(binaryStringOfIndex,"1");
if(list.size()== desiredNumberofElementsInSubset){
List<Integer> subset = new ArrayList<Integer>();
for (int j = 0; j < list.size(); j++) {
subset.add(s.get(Integer.valueOf((String)list.get(j))));
}
listOfSubsets.add(subset);
subset = null;
}
}
for(List l : listOfSubsets)
System.out.println("listOfSubsets : " + l);
}
private static List<String> isRegExpressionExist(String label, String regEx) {
ArrayList<String> mIndex = new ArrayList<String>();
int i = 0;
for (i = 0; i < label.length(); i++) {
int j = 0;
if (label.charAt(i) == regEx.charAt(j)) {
int k = i + 1;
j++;
for (; j < regEx.length(); j++,k++) {
if (label.charAt(k) != regEx.charAt(j)) {
break;
}
}
if (regEx.length() == j) {
mIndex.add(String.valueOf(i));
}
}
}
mIndex.trimToSize();
return mIndex;
}
}
Note: if we want only the subsets whose sum to N, just add a small logic to add
the numbers in the subset Lists.I have only provided the logic to generate the
subsets of size M (here it is 3).
List of all subsets of size 3 will be as follows:
listOfSubsets : [5, 3, 6]
listOfSubsets : [2, 3, 6]
listOfSubsets : [2, 5, 6]
listOfSubsets : [2, 5, 3]
listOfSubsets : [1, 3, 6]
listOfSubsets : [1, 5, 6]
listOfSubsets : [1, 5, 3]
listOfSubsets : [1, 2, 6]
listOfSubsets : [1, 2, 3]
listOfSubsets : [1, 2, 5]
struct Node {
int data;
Node* parent;
Node(int d=0,Node* p=0):data(d),parent(p) {}
};
void reverse(vector<int>& A,int pos,int end,int S,int N,Node* pare,vector<int>& rult)
{
if (end-pos<N)
return;
if (N==1) {
for (int i=pos; i<end; i++)
if (A[i]==S) {
Node* r=new Node(A[i],pare);
while (r) {
rult.push_back(r->data);
r=r->parent;
}
delete r;
return;
}
return;
}
for (int i=pos; A[i]<(double)S/N && i<end; i++) {
Node* r=new Node(A[i],pare);
reverse(A,i+1,end,S-A[i],N-1,r,rult);
delete r;
}
}
private static int Subset(int[] ar, int sum, int subno)
{
int count=0, temp=0,index=0,subsum=0;
List<int>lt = new List<int>();
List<int> ult = new List<int>(lt);
Outer: for (int i = 0; i < subno-1; i++)
{
if (index + subno - 2 < ar.Length)
{
lt.Add(ar[i+index]);
subsum = subsum + ar[i + index];
}
}
temp = sum - subsum;
if (!lt.Contains(temp) && ar.Contains(temp))
count++;
index++;
subsum = 0;
if (lt.Count()+1 == subno)
{
lt.Add(temp);
ult.Sort();
lt.Sort();
if (!ult.SequenceEqual<int>(lt))
ult = lt.ToList();
else
count--;
}
lt.Clear();
if(index < ar.Length)
goto Outer;
return count;
}
public static void sumset(int [] array,int n,int s){
int [] tmp=new int[s];
microSoft(array,0,n,s,tmp,0,0);
}
public static void microSoft(int [] array, int current, int n,int s, int [] tmp, int count,int index){
if (current==n&&count==s){
StringBuilder sb=new StringBuilder();
for (int val:tmp){
//System.out.print(val+"+");
sb.append(val);
sb.append(",");
}
sb.setLength(sb.length()-1);
System.out.println(sb.toString());
}else if (count>=s){
return ;
}else if (current>n){
return;
} else{
for (int i=index;i<array.length;++i){
tmp[count]=array[i];
current+=array[i];
microSoft(array,current,n,s,tmp,count+1,++index);
current-=array[i];
}
}
}
public class Test {
public static void backtrackSum(int[]A , int N , int S,int sum,int indx) {
if (sum == N && S == cnt) {
for (int j = 0 ; j < cnt ; j++)
System.out.print(p[j]+" ") ;
System.out.println("") ;
return ;
}
for (int i = indx; i <A.length; i ++)
if ( sum+A[i] <= N ) {
sum+=A[i] ;
p[cnt++] =A[i] ;
backtrackSum(A,N,S,sum,i+1);
sum-=A[i] ;
cnt--;
}
}
public static void main(String ...args) {
// backtrackSum(A[],N,S,0,indx);
backtrackSum(new int [] {1,2,5,3,6},9,3,0,0);
}
}
this is a modification of subset sum algorithm where we keep track of
the size of subsets generated:
void generate_subset_sums(int *a, int sz, int N, int S) { std::vector< int > sums(N + 1, 0); std::vector< std::vector< int > > nparts(N + 1); sums[0] = 1; nparts[0].push_back(0); for(int i = 0; i < sz; i++) for(int s = N; s >= 1; s--) { if(s < a[i] || sums[s - a[i]] == 0) continue; sums[s] = 1; std::vector< int >& np = nparts[s - a[i]]; for(int j = 0; j < np.size(); j++) { if(np[j] + 1 <= S) // do not count wrong sums nparts[s].push_back(np[j] + 1); } } for(int s = 1; s <= N; s++) { printf("sums[%d] = %d [", s, sums[s]); for(int j = 0; j < nparts[s].size(); j++) { printf("%d ", nparts[s][j]); } printf("]\n"); } } int main() { int a[] = {1,2,3,4,5,7}; int sz = sizeof(a)/sizeof(int); generate_subset_sums(a, sz, 10, 3); return 1; }then we get the following:
- ? May 09, 2012sums[1] = 1 [1 ]
sums[2] = 1 [1 ]
sums[3] = 1 [2 1 ]
sums[4] = 1 [2 1 ]
sums[5] = 1 [2 2 1 ]
sums[6] = 1 [3 2 2 ]
sums[7] = 1 [3 2 2 1 ]
sums[8] = 1 [3 3 2 2 ]
sums[9] = 1 [3 3 2 2 ]
sums[10] = 1 [3 3 3 2 ]