## Microsoft Interview Question for Software Engineer / Developers Software Engineer in Tests

• 4

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
1
of 1 vote

"an array of five integers". The point was just solve for this case and test it. 32 combs aren't that bad.

Comment hidden because of low score. Click to expand.
0

If I were the interviewer, if the candidate solve it for "5 inputs" using recursive approach; I'd say "your approach is not scalable/reusable" --- what if we like to use this procedure later for some bigger input case?

So solving a problem "correctly" is not all that an interviewer seeks for sure. It must be an efficient one. Efficiency means time/space complexity, coding/testing complexity etc. Efficiency never implies for 5 input,32 cases blah blah. then someone might right a nested 5 loop!

Comment hidden because of low score. Click to expand.
0

I challenge you to show me a nested five loop solution that works for all cases.

Comment hidden because of low score. Click to expand.
0

Give "smart" challenges, not dumb shit! For this problem, as ftfish noted that it's a simple DP approach which is related to famous 0/1 knapsack problem. A DP solution will give you the result within seconds even for 1000 input array and targeting sum may be 1,000,000. You wont have to store 1000 x 1000000 entries though. To limit space, 2 rows is sufficient; so it'll take like 2 rows of 1000000 entries.

Backtracking with branch and bound (aka. pruning) may be practical, but yet can't solve the worst case inputs. So the best-known simple approach is DP.

Be smart, and challenge others to do "smart" stuffs!

Comment hidden because of low score. Click to expand.
0

That solution doesn't work. Calm down, good grief.

Comment hidden because of low score. Click to expand.
1
of 5 vote

This seems like a classic Knapsack problem:

``````public class NumberTotal
{
Hashtable cache = new Hashtable();
public int TotalWays(int[] a, int total)
{
}

int TotalWaysHelper(int[] a, int end, int total, Hashtable cache)
{
string cacheKey = end.ToString() + "." + total.ToString();
if (cache.ContainsKey(cacheKey)) return (int)cache[cacheKey];
if (end == 0)
{
if (a[0] == total || total == 0)
return 1;
else
return 0;
}
int without_end = TotalWaysHelper(a, end - 1, total, cache);
int with_end = TotalWaysHelper(a, end - 1, total - a[end], cache);

cache[cacheKey] = with_end + without_end;
return with_end + without_end;
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

What makes you think this is a classic Knapsack problem?

Comment hidden because of low score. Click to expand.
1
of 1 vote

In this problem you are trying to find different combinations that would make up a given number, similar to the knapsack problem where you are trying to find the different combination of items that can fit in a knapsack.

Nevertheless, this problem can be solved using dynamic programming similar to knapsack problem.

Comment hidden because of low score. Click to expand.
1
of 7 vote

This can be solved very easily via recursion

``````public int getNoOfWays(int [] array, int index, int value)
{
if(index == array.length && value != 0)
return 0;
else if(index == array.length)
return 1;
int count = 0;
if(value == 0)
count++;
return count+
getNoOfWays(array, index+1, value) +
getNoOfWays(array, index+1, value- array[index]) +
getNoOfWays(array, index+1, value+array[index]);
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

In C code.

``````int getNoOfWays(int array[], int length, int index, int target)
{
static int count;
if(index >= length && target != 0)
return 0;
if(target == 0)
return 1;

int x = getNoOfWays(array, length, index+1, target);
int y = getNoOfWays(array, length, index+1, target-array[index]);
int z = getNoOfWays(array, length, index+1, target+array[index]);
return x+y+z;
}``````

Comment hidden because of low score. Click to expand.
0

explain a bit plz.

Comment hidden because of low score. Click to expand.
0

and how do you come up with such recursive algos..help please..

Comment hidden because of low score. Click to expand.
0

Yes, please do tell us what is the procedure you took for solving this problem and explain the logic, it will help us in solving other problems of similar kind. Awaiting your response.
Thank you ..

Comment hidden because of low score. Click to expand.
1
of 1 vote

The time complexity exponential, and I think a DP solution is expected, any the solution has one concern of the condition that the elements are unique.

Comment hidden because of low score. Click to expand.
1
of 1 vote

python code: linear time

``````def main():
ar = [2,4,6,8]
target = 12
mp = defaultdict(int)
mp[0] = 1
for i in ar:
for k, v in mp.items():
mp[k + i] += v
mp[k - i] += v

print mp[target]
print mp``````

Comment hidden because of low score. Click to expand.
0

Ami, there is a bug in your code.

``````if(value == 0)
count++;``````

and

``````...
+ getNoOfWays(array, index+1, value)
...``````

will both add 1 when value == 0. This will lead to the same combination counted multiple times.

Try this example - getNoOfWays(new int[]{ 2, 4, 7, 8 }, 0, 6);

I have rewritten it this way. May not be the most optimal one, but it works -

``````public static int WaysToCalculateTarget(int[] arr, int value, int target, int index, bool atLeastOneElementChosen)
{
if (arr.Length == index)
{
if (target == value && atLeastOneElementChosen)
return 1;
return 0;
}

return WaysToCalculateTarget(arr, value, target, index + 1, atLeastOneElementChosen)
+ WaysToCalculateTarget(arr, value + arr[index], target, index + 1, true)
+ WaysToCalculateTarget(arr, value - arr[index], target, index + 1, true);
}

static void Main(string[] args)
{
int i = WaysToCalculateTarget(new int[]{ 2, 4, 6, 8 }, 0, 12, 0, false);
}``````

Comment hidden because of low score. Click to expand.
0

Nice Solution. Can increase time complexity by using Memoization or DP.

Comment hidden because of low score. Click to expand.
0

so that is where one has to use different logic then this,.
Check the time complexity of your solution
it is O(3^n)

``````{
T(n) = T(n-1) + T(n-1) + T(n-1) + O(1).``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Manoj's answer does not account for patterns that can be solved using negative of the element. Here is the correct algorithm

``````public class NumberTotal
{
Dictionary<string, int> cache = new Dictionary<string, int>();

int[] a = new int[] { 2, 4, 6, 8 };

public int TotalWays( int total)
{
}

int TotalWaysHelper(int end, int total)
{
string cacheKey = end.ToString() + "." + total.ToString();
if (cache.ContainsKey(cacheKey)) return (int)cache[cacheKey];
if (end == 0)
{
if (a[0] == total || total == 0 || a[0]==-1*total)
return 1;
else
return 0;
}
int without_end = TotalWaysHelper(end - 1, total);
int with_end1 = TotalWaysHelper(end - 1, total - a[end]); //possitive element
int with_end2 = TotalWaysHelper(end - 1, total + a[end]); //negative element
int with_end = with_end1 + with_end2; //total possitive and negative
cache[cacheKey] = with_end + without_end;
return with_end + without_end;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int SumCombinations(int[] input, int num)
{
int count = 0;
Hashtable ht;

for (int i = 0; i < input.Length; i++)
{
int temp = input[i];
ht = new Hashtable();

int latest = num - input[i];

for (int j = i + 1; j < input.Length; j++)
{
if (ht.Contains(input[j]))
{
count++;
}
if (latest > input[j])
{
latest = latest - input[j];
}
}
}

return count;
}``````

Comment hidden because of low score. Click to expand.
0

Please give me your inputs. Also please give me some good test cases to break the code.

Comment hidden because of low score. Click to expand.
0

Just test with the input 5, 5, 10, 2, 3, your code should return more than 4.

I am suggesting a simpler solution for this specific problem:

``````count = 0;
for (int i1 = 0;i1 <= 1;i1++)
for (int i2=0;i2<=1;i2++)
for (int i3 = 0;i3 <= 1;i3++)
for (int i4=0;i4<=1;i4++)
for (int i5 = 0;i5 <= 1;i5++)
if (i1*a[1] + i2*a[2]+i3*a[3] + i4*a[4] + i5 * a[5] == 15)
count++;

return count;``````

Comment hidden because of low score. Click to expand.
0

@silence: ur solution is nothing but SHIT! how u'll solve if number input array length is 100!
It's 0/1 knapsack based simple DP problem, with complexity O(nW), W = size of knapsack (for this problem W= 15, n = 5).

Comment hidden because of low score. Click to expand.
0

Please give me more insight on how can we solve using knaksack

Comment hidden because of low score. Click to expand.
0

@silence: Awessssssssssome code...
Are you learning to write "nested loop" in first semester in UGrad level? This site is not for practicing a 5-level nested loop in C!!!

Comment hidden because of low score. Click to expand.
0

Could u write the recurrence for 0/1 Knapsack problem?
If u understand Knapsack problem, a similar recurrence (replacing 'Max' function with 'Sum') will give the result! So first google, and grasp the basic Knapsack problem solution (DP approach).

Comment hidden because of low score. Click to expand.
0

I have a small doubt here....Knapsack (0/1 version is greedy i.e. solving it involves greedy technique..) plus it gives only one solution....how do we find out all the four pairs (for the given test case) if we use 0/1 knapsack..???

Comment hidden because of low score. Click to expand.
0

0/1 knapsack is NP-complete. No one for now can solve it in TRUE polynomial time. Greedy may give a good approximation, but not an exact solution.

Comment hidden because of low score. Click to expand.
0

abey anonymous gadhe silence has mentioned that it is only for this specific problem and just a simpler solution usko bi pata hai dp solution toh jyada bakwas mat mar
i am writing in hindi coz i know only only indians like you can be so unappreciative

Comment hidden because of low score. Click to expand.
0
of 0 vote

I haven't run the code but I think this would do the trick. See any bugs here?

``````CalculateTotalCounters(a,0,0);

int CalculateTotalCounters(int[] a, int index, int partialSum)
{
if (index == a.Length) return 0;
// increment count if current permutation plus this element adds to 15 +
//    count including this element from remaining permutations
//    count not including this element from remaining permutations.
return (((partialSum + a[index]) == 15) ? 1 : 0) +
CalculateTotalCounters(a,index+1,partialSum+a[index]) +
CalculateTotalCounters(a,index+1,partialSum));
}``````

Comment hidden because of low score. Click to expand.
0

did run wonderfully.. brilliant solution...
executable version of this code provided below.

``````#include <iostream>

using namespace std;

template<typename T, int size>
int GetArrLength(T(&)[size])
{return size;}

int CalculateTotalCounters(int* a, int index, int partialSum, int len)
{
if (index == len) return 0;

// increment count if current permutation plus this element adds to 15 +
//    count including this element from remaining permutations
//    count not including this element from remaining permutations.

return (((partialSum + a[index]) == 15) ? 1 : 0) + CalculateTotalCounters(a,index+1,partialSum+a[index],len) + CalculateTotalCounters(a,index+1,partialSum,len);
}

void main()
{
int ar[] = {5, 5, 10, 2, 3};
cout << CalculateTotalCounters(ar,0,0,GetArrLength(ar)) << "\n";
}``````

Comment hidden because of low score. Click to expand.
0

Recursion sucks for big input! It's not pseudo-polynomial, but exponential as it simulates all possibility of 2^n combinations.

Comment hidden because of low score. Click to expand.
0

@ericcoder: hey ur code is again simply checks all the combinations. I think there is a much better way to solve it...

Comment hidden because of low score. Click to expand.
0

If the interviewer says you can assume the array has only 5 elements, I actually think this is a very legitimate solution. Why over-engineer? Who cares if it's O(2^n) vs O(n) when it's only 5 elements? If the interviewer cared so much about the time complexity, then he just shouldn't have said the array is 5 elements in the first place, which he probably will right after you offer this recursive version.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why would an interviewer ask (and some layman post on careercup) such a question, if solution is so monotonous?

Guys/Gals, bring some tricks into it instead of pasting your horrible code..

Comment hidden because of low score. Click to expand.
0
of 0 vote

@Meenu I dont see anything wrong in your code. It works for all the combinations os input. Guys any comment..how can we solve this problem in a different way.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Let f[i][j] be the number of combinations of the FIRST I numbers suming up to J.
f[i][j]
=
f[i-1][j-a[i]] //a[i] is selected. of course only if j>=a[i]
+
f[i-1][j] //a[i] isn't selected

The basic case is f[0][0]=1

Comment hidden because of low score. Click to expand.
0

good one. Here is its implementation:
ideone.com/lUgZz

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int input[5] = {5,5,10,3,2};
int comb(int sum, int cnt)
{
if (cnt == 0 && sum)
return 0;
else if(sum == 0)
return 1;

int i,n;
int tempsum=0;
for (i=cnt-1; i>=0; i--)
{
tempsum += comb(sum - input[i], i);
}
return tempsum;
}``````

Comment hidden because of low score. Click to expand.
0

Guys, I wanted to write the algo but the code is so simple to walk through so didn't feel the need for that.

Please lemme know if someone doesn't get it...

Comment hidden because of low score. Click to expand.
0

Guys, I wanted to write the algo but the code is so simple to walk through so didn't feel the need for that.

Please lemme know if someone doesn't get it...

Comment hidden because of low score. Click to expand.
0

Let's say there're 50 numbers instead of 5.

Comment hidden because of low score. Click to expand.
0

@ftfish: good challenge :)
I can't understand why job seeker's DO NOT like to consider complexity of a solution at all! As if solving a problem is ALL, no matter even their solutions may run till end of the world!!!

Comment hidden because of low score. Click to expand.
0
of 0 vote

int func(void)
{
int i,j,a[5],b[17];
for(i=0;i<17;i++)b[i]=0;
for(i=0;i<5;i++)cin>>a[i];
for(i=4;i>=0;i--)
{
for(j=15-a[i];j>0;j--)
{
if(b[j])
b[j+a[i]]+=b[j];
}
b[a[i]]+=1;
}
return(b[15]);
}

Comment hidden because of low score. Click to expand.
0

Ur code resulted into segmentation fault

Comment hidden because of low score. Click to expand.
0

Can you please explain the logic!!!

Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int i=0;i<a.length();i++)
{
for(j=15-a[i];j>0;j--)
{
if(b[j])
{
b[a[i]+j]+=b[j];
}
b[a[i]]+=1;
}
}

after this print b[15]; :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int i=0;i<a.length();i++)
{
for(j=15-a[i];j>0;j--)
{
if(b[j])
{
b[a[i]+j]+=b[j];
}
b[a[i]]+=1;
}
}

after this print b[15]..

Comment hidden because of low score. Click to expand.
0
of 0 vote

this is O(n^2) how much time complexity was required??

Comment hidden because of low score. Click to expand.
0
of 0 vote

this is O(n^2) how much time complexity was required??

Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys I feel the first solution given by meenu works well for longs inputs as well. it has time complexity of O(n2) with extra space.

Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="c++" line="1" title="CodeMonkey42271" class="run-this">#include<iostream>
using namespace std;
#include<cstdlib>
#include<algorithm>

int count(int a[],int i,int sum,int l)
{
static int ctr=0;
if(sum==0) {ctr++;return 0;}
if(i==l+1) return 0;
if(sum-a[i]>=0 && i < l) {count(a,i+1,sum-a[i],l);}
if(i < l) {count(a,i+1,sum,l);}
return ctr;
}

int main(){
int n,sum;
//cout<<"enter size of array and sum\n";
cin>>n>>sum;
int a[n];
//cout<<"enter the array:\n";
for(int i=0;i<n;i++) cin>>a[i];

int l=sizeof(a)/sizeof(int);
int k=count(a,0,sum,l);
cout<<"no of combinations is "<<k<<endl;
return 0;
}</pre><pre title="CodeMonkey42271" input="yes">
5 15
5 5 10 2 3
</pre>

Comment hidden because of low score. Click to expand.
0
of 0 vote

int count(int a[],int i,int sum,int l)
{
static int ctr=0;
if(sum==0) {ctr++;return 0;}
if(i==l+1) return 0;
if(sum-a[i]>=0 && i < l) {count(a,i+1,sum-a[i],l);}
if(i < l) {count(a,i+1,sum,l);}
return ctr;
}

Comment hidden because of low score. Click to expand.
0

@TILU,
Please don't put these kind of absurd variable name. As a programmer its ur code readable.You should follow coding guide lines

Comment hidden because of low score. Click to expand.
0

Every once in a while I come across a comment that I just can't resist not responding to. What's so bad about these variable names?
(1) "a" for array
(2) "i" for index
(3) "sum" - self explanatory
(4) "l" for length

The "l" for length is the only one I had problem with, because it so resembles a 1. The "i" isn't so bad because it's a typical variable for iteration. The C/C++ camp just likes to use abbreviations while Java likes to spell the whole word out...

Comment hidden because of low score. Click to expand.
0
of 0 vote

combinedsum(int in,int* out,int level,int givensum, int len,int start)
{
static ctr=0;
int sum=0;
for(int i=start;i<len;i++)
out[level]=in[i];
for(int j=0;j<level;j++)
sum+=out[j];
if(sum==givensum)
ctr++;
combinedsum(in,out,len,level+1,i+1);
}
}

what do you people think of this is it corretc??..n acc to me its complexity= O(n^2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry..just replace recursive call by -
combinedsum(in,out,level,givensum,len,i+1);

Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="c++" line="1" title="CodeMonkey43267" class="run-this">//Using Backtracking.
#include<iostream>
#include<stdlib.h>
#include<string.h>

int subSetSum ( int *a, int size, int ssum)
{
int pos,csum,result,*flag,i;

flag=(int*) malloc(sizeof(int)*size-1);

if(ssum==0)
return 1;

result=0;
csum=0;
for(i=0;i<size;i++)
{
csum+=a[i];
flag[i]=1;
}
pos=size-1;

while(pos>=0)
{
if(csum>=ssum || pos>=size-1)
{
if(csum==ssum)
result++;
while(flag[pos]!=1 && pos >=0)
pos--;
if(pos<0)
return result;
csum-=a[pos];
flag[pos]=0;

}
else
{
if(pos<size-1)
{
pos++;
csum+=a[pos];
flag[pos]=1;
}
}
}
return result;
}

int main()
{

int a[5]={5,5,10,2,3},result;

result=subSetSum(a,5,15);
printf("result is %d\n",result);

return 0;
}
</pre><pre title="CodeMonkey43267" input="yes">
</pre>

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
int a[]={5,5,10,2,3}; //array declared globally

void check(int start,int end,int num,int sum,int *count)
{
int i;
if((start>end) || (num>sum))
return;

if(num==sum)
{
(*count)=(*count)+1;
return;
}
else
{
for(i=start;i<end;i++)
{
check(i+1,end,num+a[i],sum,count);
}
}
return;
}

void call(int sum)
{
int count=0; //count variable contains the resulting number of combinations
int num,i;

for(i=0;i<5;i++)
{
num=a[i];
check(i+1,5,num,sum,&count);
}
printf("count:%d",count);
}

void main()
{
clrscr();
call(15); //Sum is sent as parameter
getch();

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Using recursion,we can get the result....Its a running code...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here we go......I have run this code ,it works man

``````import java.util.Scanner;

class ABC
{
static int arr[],sum,ways=0;
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int x;
System.out.println("Enter the array size");
x=sc.nextInt();
arr=new int[x];
for(int i=0;i<x;i++)
{
System.out.println("Enter the values");
arr[i]=sc.nextInt();
}
System.out.println("Enter the target sum");
sum=sc.nextInt();
for(int i=0;i<arr.length;i++)
findWays(0,i);
System.out.println("The no. of ways are  "+ways);
}
public static void findWays(int curr_sum,int start)
{
curr_sum=curr_sum+arr[start];
if(curr_sum==sum)
{
++ways;
return;
}
else if(start==arr.length-1 || curr_sum>sum)
return;

for(int i=start+1;i<arr.length;i++)
findWays(curr_sum,i);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a bit set based on the number of entries in the array.
four 4 entries.
0000
0001
0010
0011
1111

use 1 as a on bit in array find the sum, return all such bit pattern where sum is 15.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

he is simply talking about O(2^n) solution

dynamic knapsack solution can solve it in O(n^2) time;

Comment hidden because of low score. Click to expand.
0
of 0 vote

@Gullu THere is a bug in your code i think. You need to remove the (condition start != arr.length-1 || currentsum > sum) since you can even have a combination for sum 5 as 2,3,5,-3,-2 you can have (2,3),(2,3,5,-2-3) which your current code wont count since 2+3+5 > sum hence it wudnt go further, (2,3,5,-2,-3), (3,5,-3)
I am not sure if it wud handle (2,5,-2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

please send test case for this

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
using namespace std;
int n;
int target = 12;

int * solution;
int sol_nums = 0;
int part_sum = 0;
void Solve(int * a, int n, int cur)
{
if (cur == n)
{
if (part_sum == target)
{
sol_nums ++;
}
return;
}
solution[cur] = -1;
part_sum -= a[cur];
Solve(a, n, cur + 1);
part_sum += a[cur];

solution[cur] = 0;
Solve(a, n, cur + 1);

solution[cur] = 1;
part_sum += a[cur];
Solve(a, n, cur + 1);
part_sum -= a[cur];

}

int main()
{
int a[] = {2,4,6,8};
int n = sizeof(a) / sizeof(int);
solution = new int[n];
Solve(a, n, 0);
cout << sol_nums << endl;
delete solution;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

Its time complexity is exponential.
Also if I am understanding your logic, there is one bug.

Second instance of "part_sum += a[cur];"
should not be there.

Comment hidden because of low score. Click to expand.
0

it must be there for backtracing.

Comment hidden because of low score. Click to expand.
0

O(3^N). If N is greater than around 20, you're toast.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution can be based od dynamic programming: three dimensional table, where on pozition i, j, is boolean value, whethrer numbers on positions from i to j can sum to s. This is O(n^2 *S), so pseudopolynomial algorithm.

Comment hidden because of low score. Click to expand.
0

@tpcz, How is this problem not inherently exponential? The numbers from positions i to j can generate 3 ^ (i+j-1) different sums, depending on where you put the minus signs and/or omit numbers. How does your DP matrix look for the use case of target 12 and elements 9999, 9998, 11? Aren't there 27 booleans at play here?

Comment hidden because of low score. Click to expand.
0

@showell30, OP said pseudopolynomial, which is means that it is exponential in the number of bits in S. If S is large, the algorithm blows up.

Comment hidden because of low score. Click to expand.
0

Here's a pseudopolynomial solution that updates counts:

``````from collections import defaultdict

def num_subsets(a, target):
a = map(abs, a)
a.sort()
counts = defaultdict(int)
counts[0] = 1
for elem in a:
new_counts = defaultdict(int)
for k in counts:
new_counts[k+elem] += counts[k]
new_counts[k-elem] += counts[k]
new_counts[k] += counts[k]
counts = new_counts
return counts[target]

arr = [-5, 1, 2, 3, 4, 6, 7, 8]
target = 12
print num_subsets(arr, target)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Works well.

``````#include <iostream>

using namespace std;

void makeCombinations(int**, int, int , int&);

int const TARGET=12;
int const ARR[]={2,4,6,8};
int const ARR_SIZE=4;

int main (){

int** combinations = new int*[ARR_SIZE];

for (int i=0;i<ARR_SIZE;i++){
combinations[i]=new int[3];
combinations[i][0]=ARR[i];
combinations[i][1]=ARR[i]*-1;
combinations[i][2]=0;
}
int ways=0;
makeCombinations(combinations,0,0,ways);
cout << ways << endl;
for (int i=0;i<ARR_SIZE;i++)
delete [] combinations[i];
delete [] combinations;
}

void makeCombinations(int** combinations,int depth,int sum, int& ways){
if (depth==ARR_SIZE){
if (sum==TARGET)
ways++;
return;
}
for (int i=0;i<3;i++)
makeCombinations(combinations,depth+1,sum+combinations[depth][i],ways);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NumWays {
public static int numOfper(int[] num,int target,int low,int high){
int count=0;
if(low>high)
return 0;
if(num[low]==target)
count++;
int zero=numOfper(num,target,low+1,high);
int minu=numOfper(num,num[low]+target,low+1,high);
}

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] num={2,4,6,8};
//System.out.println(getNoOfWays(num,0,12));
System.out.println(numOfper(num,12,0,2));
}
}
this return 4,but problem is time complexity: O(3^n)
anyone has better algorithms?

Comment hidden because of low score. Click to expand.
0
of 0 vote

are the operations limited to "+" and "-" can we use other operations like "*", "/", "%" etc..,

Comment hidden because of low score. Click to expand.
0
of 0 vote

I originally downvoted this question, because it's pretty poorly specified, but I upvoted it back. The author doesn't really make it clear what constitutes a "distinct" solution. For example, why is 6 + 8 - 2 = 12 considered a solution, but 8 + 6 - 2 = 12 isn't? Are we allowed to use a negative sign in front of the first element? How about other operators? If the target number is 0, then can we say that our solution is to add up none of the numbers?

My inference is that the problem boils down to this. For each number, it can either contribute itself to the sum, its negative to the sum, or nothing to the sum. So there are 3^N possibilities to consider. I would do simple recursion with these pseudo-coded relationships:

``````f([], 0) = 1
f([], a) = 0 whenever a is not zero
f([x|rest], n) = f(rest, n+x) + f(rest, n) + f(rest, n-x)``````

In my notation [x|rest] means you have a list of at least length 1 where x is head and "rest" denotes the remainder of the elements in the list. I think the problem is ambiguously defined if either your target is zero or your list is empty, but setting up the degenerate cases correctly makes the recursion work.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a java version. Use and subtract the digit from the target and recursively call the
array for rest of items that adds upto target - digit.

``````public class SumTarget {

static int target_total = 12;
static boolean[] used = { false, false, false, false, false, false, false };
static int arr[] = { 1, 2, 3, 4, 6, 7, 8 };

public static void main(String[] args) {
for (int i = 0; i < arr.length; i++) {
sumIt(i, target_total);
}
}

public static void sumIt(int index, int target) {

//Mark Used
used[index] = true;
target = target - arr[index];

if (target == 0) {
// We are at zero already
for (int j = 0; j < used.length; j++) {
if (used[j])
System.out.print(arr[j] + " , ");
}
System.out.println();
return;
}
for (int i = index + 1; i < arr.length; i++) {
sumIt(i, target);
}
used[index] = false;
}
}``````

Comment hidden because of low score. Click to expand.
0

You don't seem to be accounting for negative numbers at all. Try transcribing this to Java:

``````f(target, list) = f(target-head, rest) + f(target, rest) + f(target+head, rest)
f(0, []) = 1
f(target != 0, []) = 0``````

Comment hidden because of low score. Click to expand.
0

Not sure I understood your concern correctly.
I assume the list the sorted in the first place. As long as the sum of negative and positive number == 0, it is going to print out correctly.
I put in the following in the above program

``````static boolean[] used = { false, false, false, false, false, false, false, false };
static int arr[] = {-2, 1, 2, 3, 4, 6, 7, 8 };``````

,
It gives me
-2 , 1 , 2 , 3 , 8 ,
-2 , 1 , 2 , 4 , 7 ,
-2 , 1 , 3 , 4 , 6 ,
-2 , 1 , 6 , 7 ,
-2 , 2 , 4 , 8 ,
-2 , 3 , 4 , 7 ,
-2 , 6 , 8 ,
1 , 2 , 3 , 6 ,
1 , 3 , 8 ,
1 , 4 , 7 ,
2 , 3 , 7 ,
2 , 4 , 6 , 7 ,
4 , 8 ,
as output.

Comment hidden because of low score. Click to expand.
0

I get it!! I am only adding up and not subtracting. Let me see whether I can modify the code.

Comment hidden because of low score. Click to expand.
0

Copying the idea above from zyfo2 on March 16, 2013, add the negative of the original array into a new array to look like this will solve the problem.

``static int arr[] = {-8, -7, -6, -4, -3, -2, 1, 2, 3, 4, 6, 7, 8 };``

Comment hidden because of low score. Click to expand.
0

@JDev, See my comment to @zyfo2. You are not only turning a 3^N problem into a (2*2)^N problem, but you're also incurring a lot of work to sift through redundant solutions. Let's say 4 is not part of the ultimate answer. You'll get a bogus solution that has 4 and -4 from zyfo2's hacky solution before the post-processing step. And it gets even worse. Consider a target of 1 and the input [1,4,6]. The only valid solution to the original problem is [1], but you'll have to exclude [1,4,-4], [1,6, -6], and [1,4,-4,6,-6] in your post-processing. It gets even nastier for [1,-4,4,6].

Comment hidden because of low score. Click to expand.
0

Oops, you can also solve the original problem with 6-4-1, but hopefully you get the idea. Introducing the additive inverses leads to solutions where the same original number gets represented twice (once for both signs), when it should have been represented zero times, and you end up wasting precious CPU to sift through the duplicated scenarios that only exist because you crufted up the array in the first place.

Comment hidden because of low score. Click to expand.
0

showell I agree with you. With a slight modification in the code, I could achieve this. Basically doing recursion, but repeating for a negated value and a positive value

``````public class SumTarget {

static int target_total = 12;
static boolean[] used = { false, false, false, false, false, false, false, false};
static boolean[] usedNegative = { false, false, false, false, false, false, false, false};
static int arr[] = {-5, 1, 2, 3, 4, 6, 7, 8 };

public static void main(String[] args) {
for (int i = 0; i < arr.length; i++) {
sumIt(i, target_total, true);
sumIt(i, target_total, false);
}
}

public static void sumIt(int index, int target, boolean sign) {
//Mark Used
used[index] = true;
int current = 0;
if(sign)
{
usedNegative[index] = true;
current = -arr[index];
}
else
{
current = arr[index];
}
target = target - current;

if (target == 0) {
// We are at zero already
for (int j = 0; j < used.length; j++) {
if (used[j])
{
if(usedNegative[j])
{
System.out.print("-" + arr[j] + " , ");
}
else
{
System.out.print(arr[j] + " , ");
}
}
}
System.out.println();
return;
}
for (int i = index + 1; i < arr.length; i++) {
sumIt(i, target, true);
sumIt(i, target, false);
}

usedNegative[index] = false;
used[index] = false;
}

}``````

Comment hidden because of low score. Click to expand.
0

@JDev, That seems fairly understandable. This is my take on it, where I try to make it very explicit that I'm iterating through all 3**N possibilities:

``````def subsets(a, target):
a = map(abs, a)
for i in range(3 ** len(a)):
bits = []
n = i
for j in range(len(a)):
# make the bits collate nicely by
# inserting at the front
bits.insert(0, n % 3)
n /= 3

result = []
sum = 0
for j, bit in enumerate(bits):
if bit == 0:
result.append(-1*a[j])
sum += -1 * a[j]
elif bit == 2:
result.append(1*a[j])
sum += a[j]
if sum == target:
yield result

arr = [-5, 1, 2, 3, 4, 6, 7, 8]
target = 12
for solution in subsets(arr, target):
print solution``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

O(2^N), no recursion, no caching

``````package questions;

public class CalculateTarget {

public static void main(String[] args) {
System.out.println(waysToTarget(new int[]{2,4,6,8}, 12));
System.out.println(waysToTarget(new int[]{0,10,20}, 30));
System.out.println(waysToTarget(new int[]{-6,-4,-2,0}, -2));
}

/**
* We need to account for both positive and negative of each value.
* The intuition here is that we simply treat the negative values
* like the second half of an extended array. Then this problem
* simplifies to finding each member of the powerset such that the
* sum of the members equals the target. This we can do by iterating
* from zero to 2^N, where N is the size of the extended array.
*/
public static int waysToTarget(int[] a, int target) {
int ways = 0;
int bits = a.length*2;
int halfbits = a.length;
// treat negative values like distinct values
int[] ary = new int[bits];
// mask to help ensure we don't use both x and -x
for(int i=0;i<halfbits;++i) {
ary[i] = a[i];
}
int next = halfbits;
for(int i=0;i<halfbits;++i) {
// if zero is present, don't duplicate
if(a[i] == 0) {
--bits;
}
else {
ary[next++] = -1*a[i];
}
}
// iterate powerset, discarding +/- duplicates
int ceiling = (int) Math.pow(2, bits);
for(int i=0;i<ceiling;++i) {
int hibits = i >> halfbits;
int lobits = i & himask;
// if no duplicate bits set
if((hibits & lobits) == 0) {
// calculate the sum for the set bits
int sum = 0;
for(int j=0;j<bits;++j) {
sum += ary[j];
}
}

if(sum == target) ++ways;
}
}

return ways;
}

}``````

Comment hidden because of low score. Click to expand.
0

This is not 2^N. It's 2^(2*N), otherwise known as 4*N. Why not just solve this in 3^N, iterating through trinary numbers 0 through 3^N-1.

0 bit = use neg
1 bit = don't use
2 bit = use pos

Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be seen as a variation of knapsack problem. Find an article about this problem in the wiki: Subset sum problem.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int dp[W+1];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i=0; i < n; i++)
for (int j=W; j>=a[i]; j--)
dp[j] += dp[j-a[i]];
return dp[W];``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

a bottomup solution:

``````int f(int *a, int n, int tar)
{
if(n <= 0)
return 0;

map<int, int> m;

m[a[0]] = 1;
m[-a[0]] = 1;
m[0] = 1;

for(int i = 1; i < n; i++)
{
map<int, int> t = m;
m.clear();

for(map<int, int>::iterator it = t.begin(); it != t.end(); it++)
{
m[it->first] += it->second;
m[it->first + a[i]] += it->second;
m[it->first - a[i]] += it->second;
}
}

return m[tar];
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````one possible solution i found using "sum of subset" with little modification to this, probably there will be better solution in terms of time complexity then let me know...

my code is
#include <stdio.h>

void countPossibleSolution(int *source, int length, int sumupto, int target, int i, int *count )
{
if(sumupto == target )
(*count)++;

if( i < length && ( sumupto + source[i] ) <= target  )
{
countPossibleSolution(source, length, sumupto+source[i], target, i+1, count);

countPossibleSolution(source, length, sumupto- source[i], target, i+1, count);
}
if (i < length && sumupto != target)
countPossibleSolution(source, length, sumupto, target, i+1, count);
}

int main()
{
int arr[]={1,2,3,4,5,6,9,10};
//int arr[]={2,4,6,8};
int len = sizeof(arr)/sizeof(arr[0]);
int solution[len];
int target = 12, count=0;
countPossibleSolution(arr, len, 0, target, 0,  &count);

printf("No of possible sum is %d\n ", count);

return 0;
}
You can see the o/p here
h+t+t+p://ideone.com/FCyWuj#view_edit_box``````

Comment hidden because of low score. Click to expand.
0

thanks

Comment hidden because of low score. Click to expand.
0

please let me no why negative vote, before performing negative vote look a while that the code is working fine , if you want give any suggestion then comment don't down-vote the answer.

Comment hidden because of low score. Click to expand.
-2
of 4 vote

for(i=0;i<a.length;i++)
{
int sum =0 ;
for(j=i+1;j<a.length;j++)
{
if(a[i]+a[j] == 12)
count++;
if(a[j] + sum == 12)
count++;
sum += a[i] + a[j];
}

}

Comment hidden because of low score. Click to expand.
0

and what if array is {1, 2, 4, 5, 6} and the target is 12?
this solution will miss 1+2+4+5.

and for unsorted array it won't work either.

Comment hidden because of low score. Click to expand.
0

it will work for that also
just one modification needed is we have remove a[i] from each time we are adding it to sum

Comment hidden because of low score. Click to expand.
-2
of 2 vote

A upbottom solution?

int f(int *a, int n, int tar)
{
if(n==1)
return abs(a[0]) == abs(tar) || tar == 0 ? 1 : 0;

return f(a, n-1, tar) + f(a, n-1, tar+a[n-1]) + f(a, n-1, tar-a[n-1]);
}

Comment hidden because of low score. Click to expand.
-2
of 8 vote

just add the negative values to the original array to become subset sum problem
and avoid possible duplicate solutions

Comment hidden because of low score. Click to expand.
0

good approach, +1

Comment hidden because of low score. Click to expand.
1
of 1 vote

That transformation is incorrect, consider the original array is {1,2}, after putting netative numbers , it will be {1,2,-1,-2}, for target 1, there will be three combinations : 1, 2 + (-1), 1 + 2 + (-2), while in the original array, there are only two combinations: 1 and 2 + (-1). They are not equivalent.

Comment hidden because of low score. Click to expand.
0

yup, since there are no duplicates; solution: before printing/storing result subsets, we can examine them to make sure they do not contain +ve and -ve entry of the same number.

Comment hidden because of low score. Click to expand.
1
of 1 vote

But what happens if the input array contains a number with both +ve and -ve entries. In the question, they never said that the input array will have only positive numbers.

Comment hidden because of low score. Click to expand.
0

I mean the negative to the original number. if it's negative originally, just add the positive ones.

Comment hidden because of low score. Click to expand.
1
of 1 vote

@zyfo2, If you approach this problem directly, it's 3 to the N, so e.g. 5 values leads to 243 cases to consider. If you try to force the square peg into the round hole and add five additive inverses to your set, now you have 1024 cases to consider, many of which aren't even valid and lead to an awkward post-processing step in the case where your initial elements repeat the same absolute value. Just solve this directly.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.