Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Say we are looking for a + b + c + d = x
1. Sort the array
2. Iterate over each element of the sorted array as a
Iterate over each element of the array which is right to the a, as b
For remaining array right side of b, take two pointers from front and back
Check if c (front) + d (back) = x - a- b
if yes then you got the answer
if no and if c+d is smaller then move front pointer
if no and if c+d is greater then move back pointer
Time Complexity:
n logn for sorting the array
n*n*n for searching the sum
O(n^3) is the complexity
No extra space is required
@D3^!L Can you please help to point out any one example which will be left in this method
@Pramod ya u r right none of the combinations were left. I might hv came up with that conclusion in a hurry
Assumption: all the members of the array are unique -- this is just for simplifying the explanation, removable with no new idea involved
the idea is to look at the 4-SUM as a 1+3-SUM problem
step 1) sort the array - n log n
step 2) for every element a in the array, find if there exists triplet (b,c,d) with sum S-a
so we get the newer problem of checking for 3-SUM in an array, this is already answered in on this forum, can be done in n^2 log n, and it is the exact same reduction. look at this as 1+2-SUM problem
step 1) for every element a
step2) find a pair (b,c) such that b+c = S-a
and so on... can be generalized for any k-SUM with complexity n^(k-1) log n
i am hoping this can be done faster
sum required by using 4 elements = Z
Step 1: Find Sum of every 2 elements in a array and store it in array F[].
This takes O(n^2) time as there are n Choose 2 such combinations.
Step2: Also Hash the value of Sum with the two elements that make the sum
<(Sum),(a,b)> such that (a+b)=Sum .This allows for O(1) time retrieval of above calculated sums and the process of hashing will take O(n^2) time and space.Note that there can be more than one combination of <(a,b)> which gives same sum like 2+4=6 and 5+1=6,then we need to store both of them by appropriate modification to your hash table.
Step 3 : sort the array F. This takes time O(n^2 log n)
Step 4: We have to find a,b,c,d such that a+b+c+d=Z
Making groups of two: (a+b)=Z-(c+d); A=Z-B;
A,B are elements of array F[] as each element corresponds to a 2-element sum there and its sorted.So for each element in F[], just find if Z-(that element) is present or not by using the Hash Table.If it is output the pairs <a,b> and <c,d> from Hash Table.
Now we can Look in the Hash Table for A and B to find <a,b,c,d> pairs
Overall Complexity -
O(n^2logn) -Time
O(n^2) -Space
Assuming we are allowed sums of the form 4a[i] or 3a[i] + a[j] or 2a[i] + 2a[j] etc.
Form all possilble n^2 sums. Sort. And then find two numbers in n^2 array which sum to S.
This is O(n^2 log n).
If we need 4 distinct numbers, then we can form n*(n-1) sums with distinct numbers. (We can probably maintain which integers form each element.)
Then find two numbers in this array with sum S.
This is O(n^2 log n^2) with O(n^2) space complexity.
@ak. Yes, but we have to be careful about sums of the form a[i] + 2 a[j] + a[k]. But that can be taken care of, if we also store the indices along with the sums.
Hi SK,
Can you please explain how did u arrive at the time complexity of O(n^2 log n^2) ?
When you create an array which has sums of two integers, then number of elements in this array will be n*(n-1).
So, when we traverse this new array for finding sum of two numbers, the complexity will be O( (n*(n-1)) * (n*(n-1)) ) which is O(n4)..isnt it?
Hi Doubt,
In size of array n, we can sort the array in O(n log n).
For each element, we can do binary search of (sum - element). This also takes O(n log n).
In this scenario, we have array of size n*(n-1). So complexity is O(n^2 log n^2).
I do not understand which statement in the problem let's you assume "we are allowed sums of the form 4a[i] or 3a[i] + a[j] or 2a[i] + 2a[j] etc."
"all combination of four elements" means you choose any 4 elements from the array and check if the sum is X.
@dc360: I honestly don't understand why you would assume that either, but it does make for a fresh variation on the problem.
There is a problem with your solution. while creating array containing combination of sum of two numbers, we may end up having sum with overlapping number.
for example 3, 5, 7, 4,... is array and we are searching for 20 then we may have generated sum (3+5= 8), (5+7 =12) and both will sum to 20 which have count 5 two times.
So that best we can do is make combination of three and sort the original array and search every combination in it. i.e n^3(log(n))
@eugene The problem statement clearly states "find all combination of four elements in the array". Interpreting "4 elements in an array" to mean "one element 3 times and one more element" would be unprecedented.
Do you think a logic that's faster than the logic that loops through "N choose 4" can exist for this problem?
@dc360: The solution for the unique case (4 different indices) already is there in the answer and the followups discussed in the comments. Why don't you try reading that and see if you understand how to do that?
@eugene: I guess it is easier to type, and then discuss the (minor) variation. See the second comment targetted towards ak. That shows how to do the unique case.
I sure hope that's what the interviewer meant because with the assumption your solution is pretty cool. So say one sum is 3+9=12, then you search in sum-sorted array for 23-12=11. Say you find 11 that came from 3+8. That's why you say its 2 * 3 + 9 + 8=23. But it does not use 4 elements from array as the question asked for. You might argue that it uses any 4th element with 0 coefficient.
The solution for 4 unique indices will be tedious. (23-sum) will have to be searched multiple times until indexes used to create 'sum' are not used to create (23-sum)
Did I get that right?
@dc360: All you need to do is store the indices which were used to form the sum.
Now if you get two sums (i1, j1) and (i2, j2). You need to confirm if all are distinct. If they aren't you continue.
The idea is good, but still generates duplicates. For the above example, this is the sorted-sums arrays.
[5, 6, 7, 7, 8, 9, 9, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 14, 14, 15, 15, 16, 17, 17, 18, 19]
We need to travel this array only up to elements 23/2 i.e. 11 and search for (23-a[i]). That avoids obvious duplicates like 5-18 and 18-5. But it produces some duplicates e.g.
2, 3, 10, 8 result of searching 5 for 18.
2, 8, 10, 3 result of searching for 10 for 13.
Another thing to note is that there are several duplicate sums, all of which need to be looked at. The sums created using different indexes are valid. It becomes a hybrid of binary and sequential search in both directions. That increases the complexity from log(n). I think its reasonable to expect duplicates in the sums array.
@dc360: What does combinations of 4 mean, when you allow duplicates in the underlying set (multiset)? You are putting too much emphasis on the word combinations, when it is actually a minor hindrance. In fact, who knows what the actual question was. OP might have chosen to use that word incorrectly for all we know.
In any case, you can do an O(n) preprocessing to remove duplicates, if you are so worried.
It is still O(n^2 log n).
I suggest you think a little bit more about it.
in C#,
public Try1(int[] collection)
{
int target = 23;
int group = 4;
int[] temp = new int[group];
for (int i = 0; i < collection.Count; i++)
{
int index=0;
for (int forGroup = 0; forGroup < group-1; forGroup++)
{
index = GetIndex(collection.Count, i, forGroup);
temp[forGroup] = collection[index];
}
for (int j = 0; j < collection.Count - group; j++)
{
temp[group - 1] = collection[GetIndex(collection.Count,index, j)];
if (temp.Sum() == target)
{
Console.WriteLine(string.Join(",", temp));
}
}
}
}
private static int GetIndex(int count, int currentPos, int inc)
{
return currentPos + inc >= count ? currentPos + inc - count : currentPos + inc;
}
package amazon;
import java.util.ArrayList;
public class Give_Sum_Get_Combination_In_Array {
/*
* Given an array of integers,
* find all combination in the array whose sum is equal to a given value X.
* For example, if the given array is {10, 2, 3, 4, 5, 9, 7, 8} and X = 23,
* then your function should print “3 5 7 8″ (3 + 5 + 7 + 8 = 23).
*/
public static void Print_Result(int[] test,int aim){
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> begin=new ArrayList<Integer>();
compute_process(test,0,aim,0,result,begin);
show_result(result);
}
public static void compute_process(int[] test,int index,int aim,int currentValue,
ArrayList<ArrayList<Integer>> result,ArrayList<Integer> currentArray){
if(index==test.length){
return;
}
ArrayList<Integer> stepArray1=cloneArrayList(currentArray);
ArrayList<Integer> stepArray2=cloneArrayList(currentArray);
ArrayList<Integer> stepArray3=cloneArrayList(currentArray);
if(test[index]+currentValue==aim){
stepArray1.add(test[index]);
result.add(stepArray1);
}
stepArray2.add(test[index]);
compute_process(test,index+1,aim,currentValue+test[index],result,stepArray2);
compute_process(test,index+1,aim,currentValue,result,stepArray3);
}
public static ArrayList<Integer> cloneArrayList(ArrayList<Integer> obj){
ArrayList<Integer> result=new ArrayList<Integer>();
for(int i=0;i!=obj.size();i++){
result.add(obj.get(i));
}
return result;
}
public static void show_result(ArrayList<ArrayList<Integer>> test){
System.out.println("Results number: "+test.size());
for(int i=0;i!=test.size();i++){
int sum=0;
System.out.print((int)(i+1)+") ");
for(int j=0;j!=test.get(i).size();j++){
int num=test.get(i).get(j);
sum+=num;
System.out.print(num);
if(j==test.get(i).size()-1)
System.out.print("=");
else
System.out.print("+");
}
System.out.print(sum);
System.out.println();
}
}
public static void main(String[] args) {
int[] test={10,2,3,4,5,9,7,8};
int aim=23;
Print_Result(test,aim);
}
}
output:
Results number: 9
1) 10+2+3+8=23
2) 10+2+4+7=23
3) 10+4+9=23
4) 10+5+8=23
5) 2+3+4+5+9=23
6) 2+4+9+8=23
7) 2+5+9+7=23
8) 3+4+9+7=23
9) 3+5+7+8=23
I think "all combination of four elements" leads me to believe that you shouldn't includes sums involving less or more than 4 elements. It's not all combinations.
I implement it again, and you can define combination number.
In this case, combination number is 4.
you also can define it as 3,5.
package amazon;
import java.util.ArrayList;
import java.util.Arrays;
public class Give_Sum_Get_N_Combination_In_Array {
public static void Print_Result(int[] test,int aim,int ComNumber){
Arrays.sort(test);
ArrayList<Integer> everyResult=new ArrayList<Integer>();
ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
compute_process(test,aim,ComNumber,0,0,1, everyResult,results);
show_result(results);
}
public static void compute_process(int[] test,int aim,int ComNumber,
int index,int currentSum,int currentComNumber,ArrayList<Integer> everyResult,
ArrayList<ArrayList<Integer>> results){
if(index==test.length){
return;
}
if(currentSum>aim){
return;
}
if(currentComNumber==ComNumber){
if(currentSum+test[index]==aim){
everyResult.add(test[index]);
results.add(everyResult);
}
}
ArrayList<Integer> tmp1=copyArrayList(everyResult);
ArrayList<Integer> tmp2=copyArrayList(everyResult);
tmp1.add(test[index]);
compute_process(test,aim,ComNumber,
index+1,currentSum+test[index],currentComNumber+1,tmp1,results);
compute_process(test,aim,ComNumber,
index+1,currentSum,currentComNumber,tmp2,results);
}
public static ArrayList<Integer> copyArrayList(ArrayList<Integer> obj){
ArrayList<Integer> result=new ArrayList<Integer>();
for(int i=0;i!=obj.size();i++){
result.add(obj.get(i));
}
return result;
}
public static void show_result(ArrayList<ArrayList<Integer>> test){
System.out.println("Results number: "+test.size());
for(int i=0;i!=test.size();i++){
int sum=0;
System.out.print((int)(i+1)+") ");
for(int j=0;j!=test.get(i).size();j++){
int num=test.get(i).get(j);
sum+=num;
System.out.print(num);
if(j==test.get(i).size()-1)
System.out.print("=");
else
System.out.print("+");
}
System.out.print(sum);
System.out.println();
}
}
public static void main(String[] args) {
int[] test={10,2,3,4,5,9,7,8};
int aim=23;
int CombinationNumber=4;
Print_Result(test,aim,CombinationNumber);
}
}
public static void Find(int[] arr, int index, int[] result,int total, int arr_index){
if(index == 4){
int temp = 0;
for(int i = 0; i < result.length; i++){
temp += result[i];
}
if(temp == total)
print(result);
}else{
for(int i = arr_index; i < arr.length; i++){
result[index] = arr[i];
Find(arr, index + 1, result, total, arr_index + 1);
}
}
}
private static void print(int[] arr){
for(int i = 0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
}
public class IntegerArrayFourValueSum {
public static void main(String[] args) {
// Test some values
test(10, 2, 3, 4, 5, 9, 7, 8);
}
private static void test(int... values) {
findCombinationsOfFourWithSum(values);
}
private static void findCombinationsOfFourWithSum(int[] values) {
for (int i = 0; i < values.length - 3; i++) {
for (int j = i + 1; j < values.length - 2; j++) {
for (int k = j + 1; k < values.length - 1; k++) {
for (int l = k + 1; l < values.length; l++) {
int total = values[i] + values[j] + values[k] + values[l];
boolean match = total == 23;
if (match) {
System.out.println(values[i] + " " + values[j] + " " + values[k] + " " + values[l]);
}
}
}
}
}
}
}
public ArrayList<ArrayList<Integer>> find4Sum(int sum, int[] array){
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
int length = array.length;
for(int i = 0; i < length ; i++){
for(int j = i+1; j < length ; j++){
for(int k = j+1; k < length ; k++){
int toFind = sum- array[i]-array[j]-array[k];
boolean sign = binarySearch(toFind, array, i, j ,k);
if(sign){
ArrayList r = new ArrayList(4);
r.add(array[i]); r.add(array[j]);r.add(array[k]);r.add(array[toFind]);
result.add(r);
}else{
continue;
}
}
}
}
return result;
}
#include<stdio.h>
#include<stdlib.h>
void print(int* vector,int v_size)
{
int i;
for(i=0;i<v_size;i++)
{
printf("%d,",vector[i]);
}
}
void funhelp(int* str,int size,int* vector,int v_size,int ite,int sum,int tot_sum)
{count++;
if(v_size>4)
return;
else if(sum==tot_sum)
{
if(v_size==4)
{
print(vector,v_size);
printf("\n");
}
return;
}
else if(sum>tot_sum)
return;
else
{
int i;
for(i=ite;i<size;i++)
{
vector[v_size]=str[i];
funhelp(str,size,vector,v_size+1,i+1,sum+str[i],tot_sum);
}
}
}
void fun(int* str,int size,int tot_sum)
{
int* vector=(int*)malloc(size);
funhelp(str,size,vector,0,0,0,tot_sum);
}
int main()
{
int str[]={10, 2, 3, 4, 5, 9, 7, 8};
fun(str,8,23);
}
#include<stdio.h>
#include<stdlib.h>
void print(int* vector,int v_size)
{
int i;
for(i=0;i<v_size;i++)
{
printf("%d,",vector[i]);
}
}
void funhelp(int* str,int size,int* vector,int v_size,int ite,int sum,int tot_sum)
{count++;
if(v_size>4)
return;
else if(sum==tot_sum)
{
if(v_size==4)
{
print(vector,v_size);
printf("\n");
}
return;
}
else if(sum>tot_sum)
return;
else
{
int i;
for(i=ite;i<size;i++)
{
vector[v_size]=str[i];
funhelp(str,size,vector,v_size+1,i+1,sum+str[i],tot_sum);
}
}
}
void fun(int* str,int size,int tot_sum)
{
int* vector=(int*)malloc(size);
funhelp(str,size,vector,0,0,0,tot_sum);
}
int main()
{
int str[]={10, 2, 3, 4, 5, 9, 7, 8};
fun(str,8,23);
}
* Java
* Complexity O(n*(2^n))
public class SumMatchCombinationsFromArray {
public static void main(String[] args) {
int[] array = new int[]{-1,4,5,4,0,6,7,9,1};
printAllCombination(0, array);
}
public static void printAllCombination(int requiredSum, int... array) {
assert (array.length < 32);
for (int i = 1, sum = 0; i < (1 << array.length); i++, sum=0) {
for (int j = 0; j < array.length; j++) {
if ((i & (1 << j)) != 0) {
sum += array[j];
}
}
if (sum == requiredSum) {
System.out.print("{");
for (int k = 0; k < array.length; k++) {
if ((i & (1 << k)) != 0) {
System.out.print(array[k] + " ");
}
}
System.out.print("}");
System.out.println();
}
}
}
}
Using meet-in-the-middle approach and hash table we can achieve O(n^2) complexity. C# code:
struct Pair
{
public int x, y;
}
static IEnumerable<int[]> FindCombinations(int[] arr, int x) // meet-in-the-middle algo
{
int n = arr.Length;
Dictionary<int, List<Pair>> hash = new Dictionary<int, List<Pair>>(n * (n - 1) / 2);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
{
if (!hash.ContainsKey(arr[i] + arr[j])) hash.Add(arr[i] + arr[j], new List<Pair>());
hash[arr[i] + arr[j]].Add(new Pair { x = i, y = j });
}
foreach (int sum in hash.Keys)
foreach (Pair pair1 in hash[sum])
{
List<Pair> rest;
if (hash.TryGetValue(x - sum, out rest))
{
foreach (Pair pair2 in rest)
if (pair2.x > pair1.y)
yield return new int[] { arr[pair1.x], arr[pair1.y], arr[pair2.x], arr[pair2.y] };
}
}
}
Hello! Can Anyone help me out to improve the following code to find combinations of six equal to a givn sum?
public class myTest {
/*
* A sorting based solution to print all combination of 6 elements in A []
* with sum equal to X
*/
void myTest(int A[], int n, int X) {
int l, r;
// Sort the array in increasing order, using library function for quick start Arrays.sort (A);
/* Now fix the first 4 elements one by one and find the other 2 elements
*/
for (int i = 0; i < n - 5; i++) {
for (int j = i + 1; j < n - 4; j++) {
for (int k = j + 1; k < n - 3; k++) {
for (int m = k + 1; m < n - 2; m++) {
// Initialize two variables as indexes of the first and last elements in the remaining elements
l = m + 1;
r = n - 1;;
// To find the remaining two elements, move the index variables (l & r) toward each other.
while (l < r) {
if (A [i] + A[j] + A[k] + A[m] + A[l] + A[r] == X) {
System.out.println(A [i]+" "+A[j]+" "+A[k]+" "+A[m]+" "+A[l]+" "+A[r]);
l++;
r--;
}
else if (A [i] + A[j] + A[k] + A[m] + A[l] + A[r] < X)
l++;
else if (A [i] + A[j] + A[k] + A[m] + A[l] + A[r] > X)
r--;
} // end of while
} // end of inner for loop
} // end of outer for loop
}
}
}
// Drive program to test above functions
public static void main(String[] args) {
myTest myTest = new myTest ();
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25};
int n = A.length;
int X = 90;
myTest.myTest (A, n, X);
}
}
The problem i get with code is that I don't get the all the combinations. Thanking you in advance.
void DoFindSubNumber(int ins[], int outs[], int level, int start, int len, int number, int total)
{
for ( int i = start; i < len; i++ )
{
outs[level] = ins[i];
total += ins[i];
if ( total == number )
{
for ( int j = 0; j <= level; j++ )
printf("%d ", outs[j]);
printf("\n");
}
if ( i < len - 1 )
{
DoFindSubNumber(ins, outs, level + 1, i + 1, len, number, total);
total -= ins[i];
}
}
}
void FindSubNumber(int ins[], int len, int number)
{
int *outs = NULL;
outs = (int *) malloc(sizeof(int) * len);
for ( int i = 0; i < len; i++ )
outs[i] = -1;
DoFindSubNumber(ins, outs, 0, 0, len, number, 0);
free(outs);
}
int main()
{
int numFindSub[] = { 10, 2, 3, 4, 5, 9, 7, 8 };
FindSubNumber(numFindSub, 8, 23);
}
this one takes o(n^3logn) ...can anyone give it in n^2???
public class GivenSumInArray {
static int[] numbers= {2,3,4,5,7,8,9,10};
public static void calculateSum()
{
int low1= 0;
int high1=numbers.length-1;
int mid1=low1+((high1-low1)/2);
int x=23;
for(int i=numbers.length-1;i>mid1+1;i--)
{
for(int j=i-1;j>mid1;j--){
int sum1=numbers[i]+numbers[j];
for(int k=0;k<mid1;k++)
{
int sum2= sum1+numbers[k];
int low2= k+1;
int high2=mid1;
int requiredNum= x-sum2;
while(low2<=high2)
{
int mid2= low2+ ((high2-low2)/2);
int midVal2= numbers[mid2];
if(midVal2==requiredNum)
{
System.out.println(numbers[k]+" "+ midVal2+" "+numbers[j]+" "+numbers[i]);
break;
}
else if(midVal2>requiredNum)
high2=mid2-1;
else if(midVal2<requiredNum)
low2=mid2+1;
}
}
}
}
}
public static void main(String[] args) {
calculateSum();
}
}
int[] arr = {9,2,10,7,6,11,12,3,5,8};
for (int i = 0; i < arr.length; i++) {
int j=0;
while(j<arr.length && j!=i){
int k=0;
while(k<arr.length && k!=i && k!=j){
int l=0;
while(l<arr.length && l!=i && l!=j && l!=k){
if(arr[i]+arr[j]+arr[k]+arr[l]==23)
System.out.println(arr[i]+" , "+arr[j]+" , "+arr[k]+" , "+arr[l]);
l++;
}
k++;
}
j++;
}
}
package pre;
public class starter {
public starter() {
}
public static void main(String[] args) {
int[] arr = new int[10];
// System.out.print("aaa");
for(int i=0; i<10; i++) arr[i]=i+1;
for(int i=0; i<10; i++)
for(int j=0; j<10; j++)
for(int k=0; k<10; k++)
for(int l=0; l<10; l++)
if (
(arr[i]+arr[j]+arr[k]+arr[l]) == 12
&& arr[i] != arr[j]
&&arr[i]!=arr[k]
&&arr[i]!=arr[l]
&&arr[j]!=arr[k]
&&arr[j]!=arr[l]
&&arr[k]!=arr[l]
)
System.out.println(arr[i] + "+" + arr[j] + "+" + arr[k] + "+" + arr[l] + "= 12" );
}
}
This is a subset problem which is NP complete. Check out the wiki page for Subset_sum_problem
Best ans coming to my mind is.
1. Fist create an bit array of size(n) equal to max element of the input arrary and reset the array with all zeros.
2. Process input array elements and set the corresponding index of the array to 1 for each element.
3. now get the first element say k from the array at zeroth index.
4. Check for (n-k)th index in new array whether it is set or not.
5. If (n-k)th index is set then you get the element.
Thats it.
This is step 3 and 4
for(i=0;i<n;i++)
{
subsum=a[i]+a[i+1]+a[i+2];
loc=Binarysearch(a[],subsum);
if(loc!=i || loc!=i+1 || loc!=i+2 || loc!=-1)
{
print(a[i],a[i+1],a[i+2],a[loc]);
}
}
this takes O(n*logn)
Code is written in C language. Please note I have tried to explain logic. This code is not optimized. There can be many way to do things,
int _tmain(int argc, _TCHAR* argv[]) { int a[] = {10,2,3,4,5,9,7,8}; /*for e.g and count is 8*/ int findSum = 23; int aCount = 8; //total array elements int sum = 0; int j = 0; int index = 0; /* Example Note: code Not Optimized int a[] = {1,2,3,4}; /*for e.g find count = 7 int findSum = 7; int aCount = 4; //total array elements calculate (Array ) (sum) [1 2 3 4] 0 0 0 0 (0) 0 0 0 1 (4) 0 0 1 0 (3) 0 0 1 1 (7) --> Ans 0 1 0 0 (2) 0 1 0 1 (6) 0 1 1 0 (5) 0 1 1 1 (9) 1 0 0 0 (1) 1 0 0 1 (5) 1 0 1 0 (4) 1 0 1 1 (8) 1 1 0 1 (7) --> Ans 1 1 1 0 (6) 1 1 1 1 (10) Output should be indexes: 1) 3,2 2) 3,1,0 */ for (int i = 1; i < (( pow(2.0,aCount) - 1)); i++) /*Iterate through all possible values as shown in example*/ { sum = 0; j = i; index = aCount -1; while( j!=0 ) { if(j & 0x1) /*check for set bit*/ { sum = sum + a[index]; /*Keep on calculating sum*/ } j = j >> 1; /*right shift*/ index--; if(sum > findSum) /*sum exceeds, break from loop*/ break; } if(sum == findSum) /*we found the sum*/ { j = i; index = aCount -1; printf("Array Indexes are "); while(j!=0) { if(j & 0x1) /*check the set bit, find the array indexes*/ { printf("%d ",index); } j = j >> 1; index--; } printf("\n"); } } return 0;}
- Anonymous September 05, 2012