CareerCup

O(n^2 (log n )+m) solution, m-#outputs:

1. Generate all possible pairs ( 2 value combinations) from the array values. Sum the values of the pair and subtract it from the target sum x , in this case 4. Lets call it as T. - O(n^2)

The idea is, a pair when joined with another pair whose sum is T will form a 4 value array whose sum is 4. Since we are generating all possible pairs from the original array, a cross join will provide all the possible 4 value array. But doing a naive cross join and filter for sum 4 will incur O(n^4) runtime. But here we will join pairs only when their sum is 4, making it O(m) runtime.

2. Bucket the pairs according to their sum. E.g. <1,2> and <4,-1> paris will go in to bucket(3). -- O(n^2)

3. For each bucket (if not already joined with another bucket) get the bucket whose value is 4 - current bucket sum. E.g. Join bucket(5) and bucket(-1). In order to find the right bucket for joining, the buckets have to be sorted by their number. We can also use hash table here. -- O(n^2 log n)

4. In each joined bucket, generate all possible 4 value array from the pairs and output it - O(M)

E.g.
Input: {1,2,3,5,0,-2} , x=4 i.e. a+b+c+d=4
All possible pairs:
{<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,0>,<1,-2>
<2,2>,<2,3>,<2,4>,<2,5>,<2,0>,<2,-2>,
<3,3>,<3,4>,<3,5>,<3,0>,<3,-2>,
<4,4>,<4,5>,<4,0>,<4,-2>,
<5,5>,<5,0>,<5,-2>,
<0,0>,<0,-2>,
<-2,-2>}

Bucket(-4)
<-2,-2>
Bucket(-2)
<0,-2>
Bucket(-1)
<1,-2>
Bucket(0)
<2,-2>,<0,0>
Bucket(1)
<1,0>,<3,-2>
Bucket(2)
<1,1>,<2,0>,<4,-2>
Bucket(3)
<1,2>,<3,0>,<5,-2>
Bucket(4)
<1,3>,<2,2>,<4,0>
Bucket(5)
<1,4>,<2,3>,<5,0>
Bucket(6)
<1,5>,<2,4>,<3,3>
Bucket(7)
<2,5>,<3,4>
Bucket(8)
<3,5>,<4,4>
Bucket(9)
<4,5>
Bucket(10)
<5,5>

Buckets {-4 and 8}, {-2 and 6}, {-1 and 5}, {0 and 4}, {1 and 3}, {2 and 2}

Output of corresponding buckets:
<-2,-2,3,5>,<-2,-2,4,4>
<0,-2,1,5>,<0,-2,2,4>,<0,-2,3,3>,
<1,-2,1,4>,<1,-2,2,3>,<1,-2,5,0>,
<2,-2,1,3>,<2,-2,2,2>,<2,-2,4,0>,<0,0,1,3>,<0,0,2,2>,<0,0,4,0>
<1,0,1,2>,<1,0,3,0>,<1,0,5,-2>,<3,-2,1,2>,<3,-2,3,0>,<3,-2,5,-2>
<1,1,1,1>,<1,1,2,0>,<1,1,4,-2>,<2,0,1,1>,<2,0,2,0>,<2,0,4,-2>,<4,-2,1,1>,<4,-2,2,0>,<4,-2,4,-2>

Can be solved using hash table

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <math.h>
#include <map>

using namespace std;

struct Entry
{
int a;
int b;
};

int main () {

typedef vector<int> VI;

VI l(6);
l[0] = 1;
l[1] = 2;
l[2] = -1;
l[3] = -2;
l[4] = 5;
l[5] = 6;

sort(l.begin(), l.end());

int sumTo = 0;

typedef multimap<int, Entry> Table;//value is sum and entry is indexes

typedef pair<int,Entry> PairEntry;//in multimap each element is stored as object of pair

Table myTbl;

// N
for (int i = 0; i < l.size(); ++i)
{
// N
for (int j = i+1; j < l.size(); ++j)
{
// Const
int val = l[i] + l[j];

// A is always less than B
Entry ent = {i, j};

myTbl.insert(PairEntry(val,ent));
}
}

pair<Table::iterator, Table::iterator> range;//range is having two iterators

// Start at beginning of array
for (Table::iterator ita = myTbl.begin();
ita != myTbl.end();
++ita)
{
int lookFor = sumTo - ita->first;
// Find the complement
range = myTbl.equal_range(lookFor);//This returns iterator(for the first match) and one past the last match(iterator) in multimap
//there can be many matches so loop through between the matches

// Const bound
for (Table::iterator itb = range.first;
itb != range.second;
++itb)
{
if (ita->second.a == itb->second.a || ita->second.b == itb->second.b)
{
// No match
}
else
{
// Match
cout << l[ita->second.a] << " " << l[itb->second.a] << " "
<< l[ita->second.b] << " " << l[itb->second.b] << endl;

return 0;
}
}
}

return 0;
}

Decided to write it in Ruby (b/c why not?). This loops over the input array and adds an entry (another array) into the sums array with just that value. Then loops over the sums array taking each entry, duplicating it, and appending value to it. If the length of the new entry equals, the given length, sum is tested. Else the new entry is appended to the sums array (which will subsequently be looped over and tested same as the above).

def find_sum_combinations(array, sum=1, length=4)
  answers = []
  sums = []

  array.each do |value|
    sums << [value]

    sums.each do |sum_entry|
      new_entry = sum_entry.dup

      if new_entry.length < length
        new_entry << value
      end

      if new_entry.length == length && new_entry.inject(:+) == sum
        answers << new_entry
      elsif new_entry.length < length
        sums << new_entry
      end
    end
  end
  answers
end

>> find_sum_combinations([1,2,3,5,0,-2])
=> [[1, 0, 0, 0], [1, 1, 1, -2], [1, 2, 0, -2], [3, 0, 0, -2], [2, 3, -2, -2], [5, 0, -2, -2]]

>> find_sum_combinations([1,2,3,5,0,-2], 2)
=> [[1, 1, 0, 0], [2, 0, 0, 0], [1, 1, 2, -2], [2, 2, 0, -2], [1, 3, 0, -2], [3, 3, -2, -2], [1, 5, -2, -2]]

>> find_sum_combinations([1,2,3,5,0,-2], 1, 5)
=> [[1, 0, 0, 0, 0], [1, 1, 1, 0, -2], [1, 2, 0, 0, -2], [3, 0, 0, 0, -2], [1, 2, 2, -2, -2], [1, 1, 3, -2, -2], [2, 3, 0, -2, -2], [5, 0, 0, -2, -2], [2, 5, -2, -2, -2]]

I think it's O(n!)? This was never my strong suit.

Just a thought
Consider int array[6] = {1,2,3,5,0,-2} and o/p required should contain 4 elements.
1. Create a binary array of 6 elements with four "1".
Each 1in binary_array will correspond to the corresponding index in array.
e.g. For binary_array[6] = {0,1,0,1,1,1} we will consider the subset {2,5,0,-2}.
binary_array[6] = {0,0,1,1,1,1} we will consider subset {3,5,0,-2}
2. Generate all the combinations of binary_array.
3. If the combination has four '1' check if the corresponding sum from array is equal to the required value.

correct me if i am wrong..
can it be done through coin change problem...with the condition that the number of element for getting the sum K must be 4.

Here is what I am doing.
Passing a comb pointer which is initially initialized to memory equivalent to 4.
Now passing this comb to the function which will print all the combinations.
Please let me know if I am doing anything wrong here

void Combinations(int sum, int *arr, int n, int ctr, int *comb, int len)
{
if(n == 0)
return 0;
if(sum == 0 && ctr == 4)
{
Print(comb, len);
return 0;
}
if(arr[n] > sum)
Combinations(sum, arr, n-1, comb, len)
else
{
comb[len] = arr[n];
Combinations(sum - arr[n], n-1, ctr+1, comb, len+1);
Combinations(sum, n-1, comb, len);
]
}

It looks straight forward to me. While we'll required to get ALL combinations (including permutations and duplicates), why not 4 loops directly? In C#:

public void Prob1(int[] a, int sum)
{
int length = a.Length;
for (int i1 = 0; i1 < length; i1++)
for (int i2 = 0; i2 < length; i2++)
for (int i3 = 0; i3 < length; i3++)
for (int i4 = 0; i4 < length; i4++)
if (a[i1] + a[i2] + a[i3] + a[i4] == sum)
Debug.WriteLine("{0}, {1}, {2}, {3}", a[i1], a[i2], a[i3], a[i4]);
}

int[] numbers = new int[] { 1, 2, 3, 5, 0, -2 };

	int[] result = new int[4];

	int N = 4;
	int SUM = 1;

	void main(String[] args) {
		checkNCombinations(0, 0, 0);
	}

	private static void checkNCombinations(int i, int n, int sum) {
		n++;
		for (; i < numbers.length - (N - n); i++) {
			result[n - 1] = numbers[i];
			sum += numbers[i];
			if (n == N && sum == SUM) {
				print(result);
			} else if (n < N)
				checkNCombinations(i, n, sum);
			sum -= numbers[i];
		}
	}

int[] numbers = new int[] { 1, 2, 3, 5, 0, -2 };

	int[] result = new int[4];

	int N = 4;
	int SUM = 1;

	void main(String[] args) {
		checkNCombinations(0, 0, 0);
	}

	private static void checkNCombinations(int i, int n, int sum) {
		n++;
		for (; i < numbers.length - (N - n); i++) {
			result[n - 1] = numbers[i];
			sum += numbers[i];
			if (n == N && sum == SUM) {
				print(result);
			} else if (n < N)
				checkNCombinations(i, n, sum);
			sum -= numbers[i];
		}
	}

generate all combinations and using dynamic programming we can solve it in O(n2) with an extra space of O(n)

subset sum problem, one more condition needs to check is subset length is 4