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


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.

- Anonymous July 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- Anonymous July 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Scroll UP this page.
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!

- Anonymous July 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 22, 2010 | Flag
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)
    {
        return TotalWaysHelper(a, a.Length - 1, total, cache);
    }

    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;
    }
}

- Manoj Agarwal March 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

What makes you think this is a classic Knapsack problem?

- Epic_coder May 03, 2013 | Flag
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.

- Manoj Agarwal May 03, 2013 | Flag
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]);
}

- ami March 16, 2013 | Flag Reply
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;
}

- try March 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

explain a bit plz.

- akie July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- akie July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ..

- rohith August 02, 2013 | Flag
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.

- weijjcg September 10, 2013 | Flag
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

- gaoxiao October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
        }

- pretentious.bastard March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sigkill July 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- sonesh June 28, 2015 | Flag
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)
            {
                return TotalWaysHelper(a.Length - 1, 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;
            }
        }

- sriwantha March 18, 2013 | Flag Reply
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];
                ht.Add(latest, latest);

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

            return count;
        }

- meenu July 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- meenu July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;

- Silence July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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).

- Anonymous July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- meenu July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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!!!

- Anonymous July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- @meenu July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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..???

- sarthak July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ftfish July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ak July 26, 2011 | Flag
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));
}

- ericcoder July 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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";
}

- Anonymous July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Sunny December 11, 2012 | Flag
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..

- Nix July 21, 2010 | Flag Reply
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.

- Anonymous July 21, 2010 | Flag Reply
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
The final answer is f[5][15].

- ftfish July 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- monish.gupta1 November 06, 2011 | Flag
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;
}

- aks July 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- aks July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- aks July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Let's say there're 50 numbers instead of 5.
try your 2^n solution.

- ftfish July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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!!!

- Anonymous July 22, 2010 | Flag
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]);
}

- akshay July 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ur code resulted into segmentation fault

- Anonymous July 28, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain the logic!!!

- Anonymous July 28, 2010 | Flag
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]; :)

- insanecoder August 02, 2010 | Flag Reply
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]..

- insanecoder August 02, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous August 02, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- insanecoder August 02, 2010 | Flag Reply
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.

- manu August 04, 2010 | Flag Reply
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>

- Anonymous August 04, 2010 | Flag Reply
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;
}

- TILU August 04, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous September 04, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- Sunny December 11, 2012 | Flag
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)

- gaurav August 08, 2010 | Flag Reply
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);

- Anonymous August 08, 2010 | Flag Reply
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>

- Anonymous August 21, 2010 | Flag Reply
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();

}

- Elamaran V September 11, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Elamaran V September 11, 2010 | Flag Reply
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);
    }
}

- gullu September 18, 2010 | Flag Reply
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.

- Paul October 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain more about your idea?

- Anonymous October 03, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

- pankaj January 14, 2011 | Flag
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)

- sri January 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

please send test case for this

- john July 02, 2011 | Flag Reply
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;
}

- speedmancs March 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Nitin Gupta March 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it must be there for backtracing.

- Anonymous March 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Aurelius March 19, 2013 | Flag
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.

- tpcz March 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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?

- showell30@yahoo.com March 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Aurelius March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- showell30@yahoo.com March 20, 2013 | Flag
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);
}

- FoY March 17, 2013 | Flag Reply
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 add=numOfper(num,target-num[low],low+1,high);
int minu=numOfper(num,num[low]+target,low+1,high);
return zero+add+minu+count;
}

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?

- denny.Rongkun March 17, 2013 | Flag Reply
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..,

- funkycoder March 18, 2013 | Flag Reply
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.

- showell30@yahoo.com March 18, 2013 | Flag Reply
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;
	}
}

- JDev March 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- showell30@yahoo.com March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- JDev March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- JDev March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 };

- JDev March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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].

- showell30@yahoo.com March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- showell30@yahoo.com March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
	}

}

- JDev March 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- showell30@yahoo.com March 20, 2013 | Flag
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
		int himask = 0;
		for(int i=0;i<halfbits;++i) {
			ary[i] = a[i];
			himask |= 1 << 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) {
					int mask = 1<<j;
					if((mask&i) == mask) {
						sum += ary[j];
					}
				}
				
				if(sum == target) ++ways;
			}
		}
		
		return ways;
	}

}

- DJ March 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- showell30@yahoo.com March 24, 2013 | Flag
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.

- Stranger March 24, 2013 | Flag Reply
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];

- Anonymous October 19, 2013 | Flag Reply
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];
}

- Leo March 16, 2013 | Flag Reply
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

- Aalok March 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks

- parashar2005nitk March 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Aalok March 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 4 vote

done it for only addition
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];
}

}

- abhi March 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- J. March 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- abhi March 16, 2013 | Flag
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]);
}

- Leo March 16, 2013 | Flag Reply
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

- zyfo2 March 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good approach, +1

- maverick March 16, 2013 | Flag
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.

- speedmancs March 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- maverick March 16, 2013 | Flag
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.

- Anonymous March 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zyfo2 March 19, 2013 | Flag
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.

- showell30@yahoo.com March 19, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More