CareerCup

well, if the array has n ones - [ 1, 1, 1, 1, ..., 1 ] and the number is n/2 (assuming n is even), then we have Binomial(n, n/2) = n!/((n/2)!)^2 options, which is exponential. So a polynomial solution is not possible.

This is the typical subset sum problem that has a pseudo-polynomial solution to determine if there is a solution or not via dynamic programming. I don't know if there is a viable solution to determine the actual solution. Or could I be mistaken? AFAICT, the solution is NP-Complete.

Can you give a couple of examples? The question is not very clear.

Are all the numbers positive? Is the key always greater than the largest number/

struct node
{
	struct node *global_next;
	struct node *hash_next;
	int sum;
	int first_index;
};
static int
int_hash(int a)
{
	return (int)(((long long)(a) * 11400714819323198485ULL) >> ((sizeof(long long) * 8) - 14));
}
static void
hash_table_add(int sum, int index, struct node **hash_table, struct node **global_list)
{
	struct node *curr;
	int hash = int_hash(sum);
	for (curr = hash_table[hash]; curr != NULL; curr = curr->hash_next) {
		if (curr->sum = sum) {
			break;
		}
	}

	if (curr == NULL) {
		curr = (struct node *)malloc(sizeof(node));
		curr->sum = sum;
		curr->first_index = index;
		curr->global_next = *global_list;
		*global_list = curr;
		curr->hash_next = hash_table[hash];
		hash_table[hash] = curr;
	}
}

void find_sums(int *a, int n, int *sums, int sum_count)
{
	struct node *global_list = NULL;
	struct node **hash_table = (struct node **)malloc (sizeof(node *) * (1 << 14));
	struct node *curr;
	int i;
	int find_sum;
	int hash;

	for (i = n - 1; i >= 0; ++i) {
		for (curr = global_list; curr != NULL; curr = curr->global_next) {
			/* new entries will get added at the begining would not be issue. */
			hash_table_add(a[i] + curr->sum, i, hash_table, &global_list);
		}
		/* Add the number itself. */
		hash_table_add(a[i], i, hash_table, &global_list);
	}

	for (i = 0; i < sum_count; ++i) {
		find_sum = sums[i];
		printf("%d :", find_sum);
		while(find_sums != 0) {
			hash = int_hash(find_sum);
			for (curr = hash_table[hash]; curr != NULL; curr = curr->hash_next) {
				if (curr->sum = find_sum) {
					break;
				}
			}

			if (curr == NULL) {
				printf("not found");
				break;
			} else {
				printf("%d ", a[curr->first_index]);
				find_sum -= a[curr->first_index];
			}
		}
		printf("\n");
	}
}

Python Code: not quite easy!

def findCombinationForTarget(target, l, path):
    if target==0 and len(path)>1:
        return tuple(path)
    if target<0:
        return None
    output=""
    for i, n in enumerate(l):
        out=findCombinationForTarget(target-n, l[i+1:], path + [n])
        if out!=None and len(out)>=1:
            output+=str(out)
    return output
        
    
def findCombination(l):
    l.sort(reverse=True)
    output=""
    for i, n in enumerate(l):
        output+=findCombinationForTarget(n, l[i+1:], [])
    return output 
    
l=[2, 4, 1, 3, 8, 6,9]
print findCombination(l)

Recursive backtracking solution to this problem is really easy to code and formulate.
But I am sure interviewer will ask for something better therefore the challenge is to find some polynomial solution to this problem. Just can't figure out any DP solution for this one !!

naive recursive solution in Java:

public static List<List<Integer>> combos(int[] a, int start, int target) {
    List<List<Integer>> retval = new ArrayList<List<Integer>>();
    if(target != 0) {
      for(int i = start; i < a.length; i ++) {
        if(a[i] <= target) {
          List<List<Integer>> ls = combos(a, start + 1, target - a[i]);
          for(List<Integer> l : ls) {
              l.add(new Integer(a[i]));
          }
          retval.addAll(ls);
        }
      }
    } else {
      retval.add(new ArrayList<Integer>());
    }
    return retval;
  }

Will this function work. I am using DP here

SumSet(int sum, int *a, int n)
{
if(a[n] > sum)
{
//no need to choose this number
SumSet(sum, a, n-1);
}
else
{
//explore both the path, taking the number and not taking the number
SumSet(sum-a[n], a, n-1);
SumSet(sum, a, n-1);
}
}

Please let me know if I am doing something wrong here

Will this function work. I am using DP here

SumSet(int sum, int *a, int n)
{
if(a[n] > sum)
{
//no need to choose this number
SumSet(sum, a, n-1);
}
else
{
//explore both the path, taking the number and not taking the number
SumSet(sum-a[n], a, n-1);
SumSet(sum, a, n-1);
}
}

Please let me know if I am doing something wrong here

public class Combinations
        {
            public List<int[]> Combs { get; set; }

            public Combinations()
            {
                Combs = new List<int[]>();
            }
            public void Add(int[] item)
            {
                Combs.Add(item);
            }

            public void Add(Combinations left, Combinations right, int[] set)
            {
                List<int[]> newComs = new List<int[]>();
                foreach (int[] leftItem in left.Combs)
                {
                    foreach (int[] rightItem in right.Combs)
                    {
                        if ((leftItem.Length + rightItem.Length) <= set.Length)
                        {
                            int leftIndex = 0;
                            int rightIndex = 0;
                            List<int> unionItem = new List<int>();
                            
                            while (leftIndex < leftItem.Length || rightIndex < rightItem.Length)
                            {
                                while (leftIndex < leftItem.Length && (rightIndex == rightItem.Length || leftItem[leftIndex] <= rightItem[rightIndex]))
                                {
                                    unionItem.Add(leftItem[leftIndex]);

                                    leftIndex++;
                                }
                                while (rightIndex < rightItem.Length && (leftIndex == leftItem.Length || leftItem[leftIndex] >= rightItem[rightIndex]))
                                {
                                    unionItem.Add(rightItem[rightIndex]);
                                    rightIndex++;
                                }
                            }

                            if (AllItemsExist(unionItem, set))
                            {
                                newComs.Add(unionItem.ToArray());
                            }
                        }
                    }
                }
 
                foreach (int[] item in newComs)
                {
                    if (!Combs.Contains(item, this))
                    {
                        Combs.Add(item);
                    }
                }
            }

            private bool AllItemsExist(List<int> unionItem, int[] set)
            {
                int setIndex = 0;
                foreach(int item in unionItem)
                {
                    while (setIndex < set.Length && set[setIndex] != item)
                    {
                        setIndex++;
                    }

                    if (setIndex < set.Length && set[setIndex] == item)
                    {
                        setIndex++;
                    }
                    else
                    {
                        return false;
                    }
                }

                return true;
            }
 ///assues set is sorted in ascending order
Combinations FindCombinations(int min, int x, Combinations[] pastComb, int[] set)
        {
            if (x < min) throw new ArgumentException(x.ToString());
            if (pastComb[x - min] != null) return pastComb[x - min];

            Combinations comb = new Combinations();
            if (set.Contains(x)) comb.Add(new int[] { x } );

            if (x > min)
            {
                for (int i = min; i <= x / 2; i++)
                {
                    Combinations leftSet = FindCombinations(min, i, pastComb, set);
                    Combinations rightSet = FindCombinations(min, x-i, pastComb, set);
                    comb.Add(leftSet, rightSet, set);
                }
            }

            pastComb[x-min] = comb;
            return comb;
        }

FindCombinations(min, x, allComb, set);
List<int[]> result = allComb[x - min].Combs;

We can sort the array from smallest to largest, then for each element i, we are looking for a subset in the range [0, i) with sum equals to arr[i], which is the subset sum problem and it is NP-complete.

However, we can generate solutions with DP:
Solution(sum, i) = Solution(sum, i-1) || Solution(sum-arr[i], i-1)

The DP algorithm can be implemented bottom-up, and it's basically enumerating all possible combinations.

We could use DP if all the numbers are positive

DP[0][0] = true
for i from 1 to array.length,
for j from 1 to K
DP[i][j] = DP[i - 1][j - num[i - 1]]

then backtrack to print all the combinations