Microsoft Interview Question
Software Engineer / Developers Software Engineer in TestsCountry: United States
Interview Type: Written Test
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!
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!
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;
}
}
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.
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]);
}
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;
}
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 ..
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.
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
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);
}
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;
}
}
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;
}
Please give me your inputs. Also please give me some good test cases to break the code.
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: 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).
@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!!!
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).
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..???
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.
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));
}
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";
}
Recursion sucks for big input! It's not pseudo-polynomial, but exponential as it simulates all possibility of 2^n combinations.
@ericcoder: hey ur code is again simply checks all the combinations. I think there is a much better way to solve it...
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.
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].
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;
}
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...
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...
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]);
}
<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>
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,
Please don't put these kind of absurd variable name. As a programmer its ur code readable.You should follow coding guide lines
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...
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)
<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>
#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();
}
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);
}
}
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.
@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)
#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;
}
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.
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, 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, 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.
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)
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);
}
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?
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.
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;
}
}
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
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.
I get it!! I am only adding up and not subtracting. Let me see whether I can modify the code.
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, 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].
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.
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, 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
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;
}
}
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];
}
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
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];
}
}
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.
just add the negative values to the original array to become subset sum problem
and avoid possible duplicate solutions
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.
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.
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.
I mean the negative to the original number. if it's negative originally, just add the positive ones.
@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.
"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