CareerCup

Hi this a tested code i used using backtacking.

public class combinations {




int arr[];

int sumuptoAi(int m,int n)
{
int sum=0;
for(int i=m;i<=n;i++)
sum=sum*10+arr[i];

return sum;
}

public boolean Combinations(int start,int sum)
{



if(sum==0&&start==arr.length)
return true;

for(int i=start;i<arr.length;i++)
{


if(Combinations(i+1, sum-sumuptoAi(start, i)))
return true;

}
return false;
}






public static void main(String args[])
{


int arr[]= {2,3,7,2};
combinations obj=new combinations();
obj.arr=arr;

System.out.println(obj.Combinations(0, 239));



}





}

Brute force approach is something in these lines (basically start from individual numbers and then increase the size by 1 and repeat for the subarray) with X to be our target. However I'd be much more interested in dynamic programming solution, which appears could exist for this problem:

return foo(A, 0)

bool foo(A, startIndex) {
  for size in (1...Length-startIndex) {
    n = getNumberOfSize(startIndex, size)
    if (n + foo(A, startIndex + size) == X {
      return true;
    }
  }
  return false;
}

Using a simple example of elements [1,2,3], build a tree of prefixes of the array as below:

123
/
-12 -- 3
\
1 --23
\
2 -- 3

Traverse the tree in a DFS fashion starting from the root, each time adding up the node values and checking against the target value.

The above tree can be created using prefix arrays of the suffix array of the given array.

Build a Prefix tree and while building a tree also ignore the prefixes which are greater than the target. Like in this example {5,2,1,4,3,6,7,8} all those prefix which are greater than 333 will be ignored. 521, 5214, 52143, 521436, 5214367, 52143678 will be ignored . Only valid prefixes are 52 and 5. Similarly for for selecting prefix for child elements ignored alll the prefixes which are greater than the target. Then on that tree Perform DFS (Pre order) and check for sum on each setup.
.

You can use DP, memoization would look like this (I made the code here, so there can be some mistakes, but I think it's enough to get the idea. It could be improved so that it's not necessary to use "get_val"):

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

int a[10005], target;
map <pii, bool> mp;

int get_val(int b, int e){
	int r = 0;
	for(int i = b; i <= e; i ++)
		r *= 10, r += a[i];
	return r;
}

bool memo(int sum, int px){
	if(sum > target) return false;
	if(px == n) return (sum == target);
	if(mp.find(pii(sum, px)) != mp.end()) return mp[pii(sum, px)];
	bool ok = false;
	for(int i = px; i < n; i ++)
		ok |= memo(sum + get_val(px, i), i + 1);
	return (mp[(pii(sum, px)] = ok);
}

int main(){

	scanf("%d %d", &n, &target);

	for(int i = 0; i < n; i ++)
		scanf("%d", &a[i]);

	if(memo(0, 0)) printf("True\n");
	else printf("False\n");

	return 0;
}

I assume all numbers in the given array are nonnegtive. Following is a solution in C. Please notice that the combinations like 34352 with 56789 can result into an arithmetic overflow.

#include <stdio.h>

const int tenPower[10] = {
    1,
    10,
    100,
    1000,
    10000,
    100000,
    1000000,
    10000000,
    100000000,
    1000000000
};

//count how many digits the positive number has
int countDigits(int n)
{
    int digits = 0;
    for(; n != 0; n /= 10) ++digits;
    return digits;
}

//check if the integer array can combine into the target number
int combine(int a[], int i, int n, int target)
{
    if(i >= n) return target == 0;
    if(a[i] == 0){//a combined decimal number can not start with 0
        return combine(a, i+1, n, target);
    }

    int sum = 0;
    for(; i < n; ++i){
        //combine a number in this level
        sum = sum * tenPower[countDigits(a[i])] + a[i];
        //if already larger than target, then no need to search deeper
        if(sum > target) break;
        //search next level
        if(combine(a, i+1, n, target - sum)) return 1;
    }
    return 0;
}

int main()
{
    int a[] = {5,2,1,4,3,6,7,8}, target = 333;

    if(combine(a, 0, sizeof(a)/sizeof(a[0]), target)) puts("YES");
    else puts("NO");

    return 0;
}

I end up giving the following answer to the interviewer..

1) Create all the combination of the given input i.e for {1,2,3} = {1,2,3,12,23,123}
2) Take the numbers add it if the number is <= target value.. The numbers should be selected in such a way that it's not repeated. E.g. If I select '12' then I cannot select '1','2','23' and '123'

Please let me know if this make sense. Complexity i worst though :( but in 20 minutes this is the approach that I was able to get too..

If u want to code simple, then just create a bool set B.
B[i]=true means there will be a '+' between A[i] and A[i+]
false means there will be nothing between the two.
Time complexity is 0(2^n）