Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Here's a JS recursive solution:
function findSubset (n, m, sum, subset) {
if (sum === 0 || n.length < 1) return subset;
var n0 = n.shift();
if (n0 === sum) {
subset.push(n0);
return subset;
}
else if (n0 < sum) {
subset.push(n0);
return findSubset(n, m-1, sum - n0, subset);
}
else return findSubset(n, m, sum, subset);
}
Use the fact that addition is commutative to solve this. You don't need to try a number again if you used it higher up the recursion layer, and found it didn't work. But you do for each different prefix set of numbers.
public class SubsetSum
{
public SubsetSum()
{
}
@Test
public void testThis()
{
NavigableSet<Integer> remaining = new TreeSet<>();
Set<Integer> inUse = new HashSet<>();
remaining.add(1);
remaining.add(5);
remaining.add(8);
remaining.add(3);
remaining.add(9);
remaining.add(11);
// want 23 out of 3.
Set<Integer> result = calculateSubSetSum(remaining, inUse, 0, 23, 3);
for (Integer i: result)
{
System.out.println(i);
}
}
// Return a set of additions if successful, otherwise null.
public Set<Integer> calculateSubSetSum(NavigableSet<Integer> remaining, Set<Integer> inUse, int sum, int goal, int M)
{
if (M > remaining.size())
{
return null;
}
Set<Integer> listOfDiscardedInts = new HashSet<Integer>();
if (M == 1)
{
if (remaining.contains(goal-sum))
{
// SUCCESS!!!!
inUse.add(goal-sum);
return inUse;
} else {
return null;
}
}
else {
while (remaining.size() > 0)
{
// Always safe to take the lowest value.
Integer i = remaining.pollFirst();
// We can safely remove this int, and not return it until the end.
inUse.add(i);
listOfDiscardedInts.add(i);
Set<Integer> result = calculateSubSetSum(remaining, inUse,
sum + i,
goal, M-1);
if (result != null)
{
// We got a result!
return result;
}
// No result, try the next addition.
inUse.remove(i);
}
}
for (int i: listOfDiscardedInts)
{
remaining.add(i);
}
return null;
}
}
This is great code, but it only works if we assume the input array does not have any repeated elements. For example, if the following input array were turned into a TreeSet, you'd lose all the duplicated 3's and it would fail.
int[] input = new int[] { 3, 3, 3, 5, 6, 7};
int M = 3;
int SUM = 9;
Recursively move the input array and build each possible subset by recursively including and not-including the number at the current index.
public static ArrayList<Integer>subset(int[] input, int targetSum, int targetSize,
ArrayList<Integer> currentSet, int currentSum, int currentIndex) {
if (currentSum > targetSum) {
return null;
}
if (currentIndex == input.length) {
return null;
}
if (currentSet.size() == targetSize) {
if (currentSum == targetSum) {
return currentSet;
} else {
return null;
}
}
ArrayList<Integer> withCurrentIndexSubset = (ArrayList<Integer>) currentSet.clone();
withCurrentIndexSubset.add(input[currentIndex]);
withCurrentIndexSubset = subset(input, targetSum, targetSize, withCurrentIndexSubset,
currentSum + input[currentIndex], currentIndex++);
ArrayList<Integer> withoutCurrentIndexSubset = (ArrayList<Integer>) currentSet.clone();
withoutCurrentIndexSubset = subset(input, targetSum, targetSize, withoutCurrentIndexSubset,
currentSum, currentIndex++);
if (withCurrentIndexSubset != null) {
return withCurrentIndexSubset;
} else {
return withoutCurrentIndexSubset;
}
}
Here is the C++ version of solution using DFS.
It is using permutation algorithm with fixed length.
I am not proud of this solution though. Will post better.
Time complexity is O(N^M) where N is # of numbers in the array and M is the fixed subset.
Any critics or suggestions are welcomed.
#include<iostream>
#include<list>
using namespace std;
bool dfs(int left, list<int>&found, int max_depth, bool* marked, int *input, int len)
{
if (found.size() == max_depth)
{
if (left == 0)
{
return true;
}
return false;
}
for (int i = 0; i < len; i++)
{
if (!marked[i] && input[i] <= left)
{
left -= input[i];
marked[i] = true;
found.push_back(input[i]);
if (dfs(left, found, max_depth, marked, input, len))
{
return true;
}
left+= input[i];
marked[i]= false;
found.pop_back();
}
}
return false;
}
list<int> find_sub_set(int * input, int max_size, int sum, int len)
{
bool *marked = new bool[len];
int left = sum;
list<int> found;
for (int i = 0; i < len; i++)
{
if (!marked[i] && input[i] <= left)
{
marked[i] = true;
left -= input[i];
found.push_back(input[i]);
if (dfs(left, found, max_size, marked, input, len))
{
break;
}
marked[i] = false;
left += input[i];
found.pop_back();
}
}
return found;
}
int main()
{
int input[5] = {1,2,4,5,9};
list<int> result = find_sub_set(input, 2, 9, 5);
list<int>::iterator iter;
for (iter = result.begin(); iter != result.end(); iter++)
cout <<(*iter)<<", ";
cout<<endl;
return 1;
}
private static int[] ArraySubSum(int[] input, int num, int sum)
{
return SubSum(input, num, sum, 0);
}
public static int[] SubSum(int[] input, int num, int sum, int idx)
{
for (int i = idx; i < input.Length; i++)
{
if (num == 1 && input[i] == sum)
return new int[1] { input[i] };
else if (num > 1)
{
int[] a = new int[num];
a[0] = input[i];
var p = SubSum(input, num - 1, sum - input[i], i + 1);
for (int k = 0; k < p.Length; k++)
{
a[k + 1] = p[k];
}
if (Sum(a) == sum)
return a;
}
}
return new int[0];
}
public static int Sum(int[] arr)
{
int sum = 0;
for(int i=0;i<arr.Length;i++)
{
sum += arr[i];
}
return sum;
}
Using c#
stackoverflow.com/questions/31803275/sum-exactly-using-k-elements-solution
#include <stdio.h>
#define SIZE(a) sizeof(a)/sizeof(a[0])
int binary[100];
int a[] = {1, 2, 5, 5, 100};
void show(int* p, int size) {
int j;
for (j = 0; j < size; j++)
if (p[j])
printf("%d\n", a[j]);
}
void subset_sum(int target, int i, int sum, int *a, int size, int K) {
if (sum == target && !K) {
show(binary, size);
} else if (sum < target && i < size) {
binary[i] = 1;
foo(target, i + 1, sum + a[i], a, size, K-1);
binary[i] = 0;
foo(target, i + 1, sum, a, size, K);
}
}
int main() {
int target = 10;
int K = 2;
subset_sum(target, 0, 0, a, SIZE(a), K);
}
Here's a quick JS recursion function
function findSubset (n, m, sum, subset) {
if (sum === 0 || n.length < 1) return subset;
var n0 = n.shift();
if (n0 === sum) {
subset.push(n0);
return subset;
}
else if (n0 < sum) {
subset.push(n0);
return findSubset(n, m-1, sum - n0, subset);
}
else return findSubset(n, m, sum, subset);
}
sort the list and iterate over of each element and build a list of tuples containing the minSum and maxSum that can be made when the number is included in the desired subset
iterate of the resulting "sum" list to see which bucket the given sum fits in; eliminate the number from list if its corresponding minSum > sum or maxSum < sum and make a filtered list
recursively do the above method on the remaining list until minSum == sum or maxSum==sum or we run out of elements in the list
def subset_helper(ls, n):
subl = []
min = sum(ls[:n-1])
max = sum(ls[-(n-1):])
for i, j in enumerate(ls):
if i < n - 1:
vmin = min + ls[n-1]
else:
vmin = min + j
if i > len(ls) - (n):
vmax = max + ls[len(ls)-n]
else:
vmax = max + j
subl.append((vmin, vmax))
return subl
def find_subset(ls, s, n):
print ls, s, n
if len(ls) < n:
return "Failed 1"
elif len(ls) == n:
if sum(ls) == s:
return ls
else:
return "Failed 2"
subl = subset_helper(ls, n)
print subl
invmin = None
invmax = None
for i, v in enumerate(subl):
print i, v
if v[0] > s:
invmax = i
break
elif v[0] == s:
print 'Found subset at using min:', i
if i <= (n-1):
return ls[:n]
else:
return ls[:(n-1)] + [ls[i]]
if v[1] < s:
invmin = i
elif v[1] == s:
print "Found subset at using max:", i
if i > len(ls) - n:
return ls[-n:]
else:
return ls[-(n-1):] + [ls[i]]
print invmin, invmax
if invmin is not None and invmax is not None and invmin == invmax:
return "Failed 3"
invmin = invmin or -1
invmax = invmax or len(ls) + 1
print 'invmin,invmax', invmin, invmax
return find_subset(ls[invmin+1:invmax], s, n)
if __name__ == '__main__':
l = [0, 4, 5, 6, 14, 13, 1]
s = 14
n = 3
ls = sorted(l)
print find_subset(ls, s, n)
Starting from the lowest possible sum, work your way up by changing your subset sum by as little as possible. This is done by having a sorted draft subset then swapping the largest element for a slightly bigger element until it's too big then undo the swap and move onto a smaller element in your draft subset. This is basically brute forcing but the extra break in the loop skips the possible subsets where the sum is already too large.
public static int[] findSub(int[] nums, int n, int m, int sum) {
Arrays.sort(nums);
printArray(nums);
System.out.println("----------");
int[] subset = Arrays.copyOfRange(nums, 0, m); // Extract the first M smallest elements
int difference;
int original;
int debugCounter = 0;
for (int i = m - 1; i >= 0; i--) {
for (int j = m + 1; j < n; j++) {
printArray(subset);
System.out.println(i + " Sum = " + sum(subset));
difference = sum - sum(subset);
if (difference == 0)
return subset;
if (Arrays.binarySearch(subset, nums[j]) >= 0) {
continue;
}
original = subset[i];
subset[i] = nums[j];
if (sum - sum(subset) < 0) {
subset[i] = original;
break;
}
}
}
return subset;
}
public static int sum(int[] nums) {
int sum = 0;
for (int i : nums) {
sum += i;
}
return sum;
}
public static void printArray(int[] nums) {
for (int i : nums) {
System.out.println(i);
}
}
}
<?php
function findSubSet($inputs, $m, $sum) {
$length = count($inputs);
if ($length < $m) return null;
if ($m == 0) return [];
sort($inputs);
for( $i = 0; $i <= $length - $m; $i ++) {
$subset = array_slice($inputs, $i, $m);
$tmpSum = array_sum($subset);
if ($tmpSum == $sum) {
return $subset;
}
else if ($tmpSum > $sum) break;
}
return null;
}
var_dump(findSubSet([7,1,2,3,4,5,6,7,7,7], 4, 14));
Time: O(n(n+1)/2)=n*n
Space: n(n+1)/2 // to store the limited number of subsets
n=length(A)
sets=[ ]
for (i=0 to n-1)
newsets = [ ]
newsets.add( setof(A[i])
if(M == 1 && setof(A[i]) == SUM) print and break
foreach set in sets
s1 = sets[j].add(A[i])
if(s1.size == M && sum(s1)==SUM) print and break
newsets.add(s1); // we can also skip adding s1 if s1.size>M
sets.clear() // we dont need the old sets as we cant add next item to them
sets.addAll(newsets)
Lets say A= {1,2,3,4,5}
M=3
SUM=12
A[i] newsets sets
-----------------------------------------------------------------------------
1 {1} {1}
2 {2}, {1,2} {2}, {1,2}
3 {3}, {2,3}, {1,2,3} {3}, {2,3}, {1,2,3}
4 {4}, {3,4}, {2,3,4}, {1,2,3,4} {4}, {3,4}, {2,3,4}, {1,2,3,4}
5 {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5} {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5}
in last iteration we have {3,4,5} whose sum is 12 and size is 3.
Now we went through A only once, but for each elements we iterated over sets which is i times hence n(n+1)/2.
In the last iteration we stored n(n+1)/2 items which is the max
A[i] newsets sets
-----------------------------------------------------------------------------
1 {1} {1}
2 {2}, {1,2} {2}, {1,2}
3 {3}, {2,3}, {1,2,3} {3}, {2,3}, {1,2,3}
4 {4}, {3,4}, {2,3,4}, {1,2,3,4} {4}, {3,4}, {2,3,4}, {1,2,3,4}
5 {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5} {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5}
[−2,1,−3,4,−1,2,1,−5,4]
a=0
-2
int maxSubArray(int[] array, int sum) {
if(array==null) || array.length==0)
return 0;
int max=array[a];
int maxsofar=array[a];
if(sum==max)
return;
for(int a =1; a<array.length; a++)
maxsofar=getMax(maxsofar+array[a],array[a]);
max=getmax(max,maxsofar);
if(max==sum) {
break;
return true;
}
if(max>sum)
maxsofar=array[i];
max=array[i];
}
}
def k_subset_sum(numbers, k, total):
sorted_numbers = sorted(numbers, reverse=True)
return k_subset_sum_internal(sorted_numbers, k, total, [])
def k_subset_sum_internal(numbers, k, total, current_list):
if k == 0:
if sum(current_list) == total:
return current_list
else:
return None
sum_so_far = sum(current_list)
upper_bound = total - sum_so_far - (k - 1)
for num in numbers:
if num <= upper_bound:
current_list.append(num)
result = k_subset_sum_internal(numbers, k - 1, total, current_list)
if result is not None:
return result
current_list.pop()
return None
print k_subset_sum([6,4,5,2,3,1], 4, 10)
A Java solution:
public static Set<Integer> findSubsetSizeK( int[] set, int sum, int m ) {
Set<Integer> subset = new HashSet<>( m );
if ( set == null || set.length < m ) {
return subset;
}
return findSubsetSizeK( set, set.length-1, sum, m, subset );
}
public static Set<Integer> findSubsetSizeK( int[] set, int n, int sum, int m, Set<Integer> subset ) {
if ( getSum( subset ) == sum && m == 0 ) {
return subset;
} else if ( m == 0 || n < 0 ) {
return null;
}
if ( set[n] < sum ) {
subset.add( set[n] );
Set<Integer> subsetWithElement = findSubsetSizeK( set, n-1, sum, m-1, subset );
if ( subsetWithElement != null ) {
return subsetWithElement;
} else {
subset.remove( set[n] );
return findSubsetSizeK( set, n-1, sum, m, subset );
}
} else {
return findSubsetSizeK( set, n-1, sum, m, subset );
}
}
private static int getSum( Set<Integer> set ) {
int sum = 0;
for ( int element : set ) {
sum += element;
}
return sum;
}
public static void main( String[] args ) {
int[] set = { 3, 34, 4, 12, 5, 2 };
int sum = 19; // {12,5,2}
int m = 3;
System.out.println( "A subset for " + Arrays.toString( set ) + " that sums up to " + sum +
" with exactly " + m + " elements is: " + findSubsetSizeK( set, sum, m ) );
System.out.println();
sum = 17; // {3,12,2}
System.out.println( "A subset for " + Arrays.toString( set ) + " that sums up to " + sum +
" with exactly " + m + " elements is: " + findSubsetSizeK( set, sum, m ) );
System.out.println();
}
Scala : recursive solution with memorization
Complexity: N * M * SUM
def subset(ARR: Seq[Int], M: Int, SUM: Int): Seq[Seq[Int]] = {
if (M > ARR.length) return Seq.empty
val memo = mutable.Map.empty[(Seq[Int], Int, Int), Seq[Seq[Int]]]
def run(arr: Seq[Int], m: Int, sum: Int): Seq[Seq[Int]] = memo.getOrElseUpdate((arr, m, sum), {
if (arr.isEmpty) return Seq.empty
val head = arr.head
if (m == 1 && sum == head) return Seq(Seq(head))
if (m == 1 && sum != head) return Seq.empty
(1 until arr.length)
.flatMap(i => run(arr.drop(i), m - 1, sum - head))
.toSeq
.map(head +: _)
})
(0 until ARR.length).flatMap(i => run(ARR.drop(i), M, SUM)).toSeq
}
println(subset(Seq(3, 3, 3, 4, 4, 1, 0, 9, 0), 3, 9))
static void PrintSubsets()
{
int source[] = {1,2,3,4,5,6};
int currentSubset = (int)Math.pow(2, source.length)-1;
int total=10;
int tmp=0,noofones;
int size=4;
while(currentSubset>0)
{noofones=0;
int sum=0;
StringBuilder sb=new StringBuilder();
tmp=currentSubset;
for(int k=0;k<source.length;k++)
{
if( (tmp&1)>0)
{
sum+=source[k];
sb.append(source[k]);
sb.append(" ");
noofones++;
}
tmp>>=1;
}
if(sum==total && noofones==size)
System.out.println(total+" = "+sb.toString());
currentSubset--;
}
}
'''
On a given array with N numbers, find subset of size M (exactly M elements) that equal to SUM.
'''
import sys
import copy
def findSum(numList, size, sum, start, tmpSum, tmpList):
print str(tmpList)
result = []
if tmpSum == sum and len(tmpList) is size:
return tmpList
elif tmpSum > sum:
return []
elif len(tmpList) is size:
return []
for i in range(start, len(numList)):
tmpSum += numList[i]
tmpList.append(i)
result = findSum(numList, size, sum, i+1, tmpSum, tmpList)
if len(result):
break;
tmpSum -= numList[i]
tmpList.remove(i)
return result
def main():
numList = [1, 2, 3, 4, 5]
size = 4
sum = 10
result = findSum(numList, size, sum, 0, 0, [])
if result:
print 'Found subset of size ' + str(size) + ':' + str(result)
else:
print 'Not Found'
if __name__ == '__main__':
sys.exit(main())
Here's a recursive solution in JS
function findSubset (n, m, sum, subset) {
if (sum === 0 || n.length < 1) return subset;
var n0 = n.shift();
if (n0 === sum) {
subset.push(n0);
return subset;
}
else if (n0 < sum) {
subset.push(n0);
return findSubset(n, m-1, sum - n0, subset);
}
else return findSubset(n, m, sum, subset);
}
Here's a recursive solution in JS
function findSubset (n, m, sum, subset) {
if (sum === 0 || n.length < 1) return subset;
var n0 = n.shift();
if (n0 === sum) {
subset.push(n0);
return subset;
}
else if (n0 < sum) {
subset.push(n0);
return findSubset(n, m-1, sum - n0, subset);
}
else return findSubset(n, m, sum, subset);
}
Here's a JS recursive solution:
function findSubset (n, m, sum, subset) {
if (sum === 0 || n.length < 1) return subset;
var n0 = n.shift();
if (n0 === sum) {
subset.push(n0);
return subset;
}
else if (n0 < sum) {
subset.push(n0);
return findSubset(n, m-1, sum - n0, subset);
}
else return findSubset(n, m, sum, subset);
}
public static void main(String[] args) throws Exception {
int[] a = {5,3,2,1,0,4,9,7,8};
subSeqSumSizeM(a,3,5);
}
//On a given array with N numbers, find subset of size M (exactly M elements) that equal to SUM.
private static void subSeqSumSizeM(int[] a, int m, int sum) {
if(a == null || (a.length==0) || m<=0 || m>a.length)
return;
int answer = 0;
for(int i=0; i<m; i++) {
answer = answer + a[i];
}
for(int j=1; j<a.length-m; j++) {
if(answer == sum)
System.out.println((j-1)+ "-" + (j+m-2));
answer = answer -a[j-1] + a[j+m-1];
}
}
classic knapsack problem
- Darkhan.Imangaliev August 04, 2015dp[i][j][s] - means whether it's possible to get sum s after consideration of i elements and taking exactly j of them.
Overall complexity (N^2 * SUM)