Interview Question
Country: United States
The solution i came up with during the interview was something of this sort:
function sumTwo(array, target) { ... } //O(n) using hashing to return [x,y] such that x+y=target
function sumNK(array, k, target) {
if (k === 2 ) {
return sumTwo(array, target);
}else {
for(var i = 0; i < array.length; ++i) {
var subTarget = target - array[i];
var subArray = array.slice().splice(i, 1); //make copy and remove currently used elem
var subResult = sumNK(subArray, k - 1, subTarget);
//save possible subResult if valid and return it....
}
}
}
{{public static String getAllPosibleCombinations(int[] arr, int expectedSum, int n, StringBuilder possibleCombinations) {
if (n == arr.length) {
return possibleCombinations.toString();
}
for (int i = 0; i < arr.length; i = i + 1) {
int sum = 0;
int k = i;
int firstOperandCount = 0;
while (firstOperandCount < n) {
if (k == arr.length) {
k = 0;
}
sum+= arr[k++];
firstOperandCount++;
}
int j = k >= arr.length ? 0 : k;
while (j != i) {
if (sum+arr[j++] == expectedSum) {
possibleCombinations.append("{");
firstOperandCount = 0;
int l = i;
while (firstOperandCount < n) {
if (l == arr.length) {
l = 0;
}
possibleCombinations.append(" " + arr[l++]);
firstOperandCount ++;
}
possibleCombinations.append(" " + arr[j-1] + " }");
}
if (j == arr.length) {
j = 0;
}
}
}
return getAllPosibleCombinations(arr, expectedSum, ++n, possibleCombinations);
}
public static void main(String[] args) {
System.out.println(getAllPosibleCombinations(new int[] {0,1,2,3,4},6, 1, new StringBuilder()));
}
}
}}
{{public static String getAllPosibleCombinations(int[] arr, int expectedSum, int n, StringBuilder possibleCombinations) {
if (n == arr.length) {
return possibleCombinations.toString();
}
for (int i = 0; i < arr.length; i = i + 1) {
int sum = 0;
int k = i;
int firstOperandCount = 0;
while (firstOperandCount < n) {
if (k == arr.length) {
k = 0;
}
sum+= arr[k++];
firstOperandCount++;
}
int j = k >= arr.length ? 0 : k;
while (j != i) {
if (sum+arr[j++] == expectedSum) {
possibleCombinations.append("{");
firstOperandCount = 0;
int l = i;
while (firstOperandCount < n) {
if (l == arr.length) {
l = 0;
}
possibleCombinations.append(" " + arr[l++]);
firstOperandCount ++;
}
possibleCombinations.append(" " + arr[j-1] + " }");
}
if (j == arr.length) {
j = 0;
}
}
}
return getAllPosibleCombinations(arr, expectedSum, ++n, possibleCombinations);
}
public static void main(String[] args) {
System.out.println(getAllPosibleCombinations(new int[] {0,1,2,3,4},6, 1, new StringBuilder()));
}
}
}}
Solution in python
from itertools import combinations
def compute_sum_t_with_k(seq, k, t):
return filter(lambda x: sum(x) == t, combinations(seq, k))
Some possible optimizations that could be done are:
- Sorting the array and stop the iteration when we go over the sum.
- Keeping a counter for the sum so instead of adding the k elements we subtract one element and a new one
@tnutty2k8 cool solution but the code is counting possible subsets more than one isn't? For example, [1,2,3,4,5,7] with k 3 and t 6 would count the subset {1,2,3} three times. One for the fist call on the for loop with [2,3,4,5,7], 2, 5, another one for the second iteration [1,3,4,5,7], 2, 4 and the last one for the third iteration [1,2,4,5,7], 2, 3. Javascript is not one of my strong points and perhaps you were planning to check that elsewhere on the code sorry if that is the case this is also for me to learn :).
Edit: I read the question again and it says any so my previous comment is about counting more than once is not valid.
Cheers.
@fernando,
Youre right, I didn't implement the full details in that code, it was more meant to be a demonstration of the logic, but yea, it would still need to handle duplicates. There are few way we can enforce unique solution. One is to actually splice on the actual input array, example
array.splice(i, 1);
That way on each iteration we remove the current element which will not be present for next iteration. This also prunes some premutations.
def printCombination(list, index, op, K, sum, sumTillNow):
if sumTillNow == sum and len(op) == K:
print(op);
return;
if index >= len(list) or len(op) > K or sumTillNow > sum :
return;
op.append(list[index]);
printCombination(list, index + 1, op, K, sum, sumTillNow + list[index]);
op.pop();
printCombination(list, index + 1, op, K, sum, sumTillNow);
printCombination([1, 2, 3, 4, 5], 0, [], 2, 6, 0);
The recursive formula is good for small and constant k. Most recursion can easily be fixed for large k (n-k = constant and small). Since the binomial coefficient grows exponential if k is for example n/2 all recursive solutions are of exponential time.
To solve this, there is a naive pseudo-polynomial time algo with an upper bound O(target * n * k * k). It's much better than the recursive solutions which are exponential and it only works if the input is positive and no duplicates occur which was the problem statement.
It finds one solution if at least one exists.It works as follows:
It tracks all seen sums but at most one per number of elements and sum (because 4+2 = 6 and 5+1 = 6 both have two elements, there is no need to consider them independently in the future).
unordered_set<int> anySumOfK_poly(const vector<int>& arr, int target, int k)
{
vector<vector<unordered_set<int>>> dp(target + 1, vector<unordered_set<int>>(k));
for (int a : arr) {
for (int i = 0; i + a <= target; i++) {
for (int l = 0; l < k - 1; l++) {
if (!dp[i][l].empty() && dp[i + a][l + 1].empty() && dp[i][l].find(a) == dp[i][l].end()) { // only one solution
dp[i + a][l + 1] = dp[i][l]; // copy (at most k elements)
dp[i + a][l + 1].insert(a); // add a
if (l + 2 == k && i + a == target) return dp[i + a][l + 1]; // found a solution
}
}
}
dp[a][0] = unordered_set<int>{ a };
}
return unordered_set<int>();
}
def printCombination(list, index, op, K, sum, sumTillNow):
if sumTillNow == sum and len(op) == K:
print(op);
return;
if index >= len(list) or len(op) > K or sumTillNow > sum :
return;
op.append(list[index]);
printCombination(list, index + 1, op, K, sum, sumTillNow + list[index]);
op.pop();
printCombination(list, index + 1, op, K, sum, sumTillNow);
printCombination([1, 2, 3, 4, 5], 0, [], 4, 14, 0);
a brutforce recursive solution
- Michael O August 18, 2017