Given an array of integers and a sum, the task is to find if there exists a subsets of given array with sum equal to given sum

user_2940975 0
Viewed 115

Here is the function that i have written.

    public static boolean existsSum(int[] arr, int n, int sum){
            if(sum==0)
                return true;
            if(n<=0)
                return false;
            if(arr[n-1] == sum)
                return true;
            if(sum<0)
                return false;
            if(sum<arr[n-1])
                return existsSum(arr, n-1,sum);
            return existsSum(arr, n-1, sum-arr[n-1])  || existsSum(arr, n-1,sum)  ;
        }

This works perfectly fine. But as soon as I change last line of code like this

    public static boolean existsSum(int[] arr, int n, int sum){
            if(sum==0)
                return true;
            if(n<=0)
                return false;
            if(arr[n-1] == sum)
                return true;
            if(sum<0)
                return false;
            if(sum<arr[n-1])
                return existsSum(arr, n-1,sum);
            return existsSum(arr, n-1,sum) || existsSum(arr, n-1, sum-arr[n-1])  ;
        }

It exceeds the time limit. I can't understand what is the impact on execution time upon changing the sequence. Please help.

dynamic-programming recursion data-structures algorithm java
2 Answers

Note the fact that || is short-circuiting i.e. in a || b, if a is true, b is not evaluated.

The difference between the two operands of || is that existsSum(arr, n-1, sum-arr[n-1]) "adds" the current item to the list of items that sums to the total sum, while existsSum(arr, n-1, sum) doesn't.

In the first code snippet, if existsSum(arr, n-1, sum-arr[n-1]) is true, existsSum(arr, n-1, sum) is not even called. Imagine I call this with the array [1,2,3] and the sum 6. The first operand is going to return true every recursive call, and there is no need to evaluate the second operand.

Similarly, in the second code snippet, existsSum(arr, n-1, sum) is run first, and if true, existsSum(arr, n-1, sum-arr[n-1]) is not called. However, existsSum(arr, n-1, sum) can rarely return true on its own. What I mean by this is that for the call existsSum(arr, n-1, sum) to return true, the value true must have come from a recursive call to existsSum(arr, n-1, sum-arr[n-1]). You can verify this by analysing the different branches. (the two branches that return true are sum==0 and arr[n-1] == sum. Hopefully you'll agree both are rare) This means that backtracking (i.e. calling existsSum(arr, n-1, sum-arr[n-1])) will definitely happen for existsSum(arr, n-1, sum).

In the worst case though, these two code snippets are the same.

user_51335850

This should be O(n)

public static boolean sumExists(int [] in, int sum) {
    //You might be able to get away with just sorting the values and not copying it.
    int [] input = Arrays.copyOf(in, in.length);
    Arrays.sort(input);
    int currentSum = 0;
    int startIdx = 0;
    for (int i = 0; i < input.length; i++) {
        if (currentSum > sum) {
            while (currentSum > sum && startIdx < i) {
                currentSum -= input[startIdx++];
            }
        }

        if (currentSum == sum) {
            return true;
        } 
        currentSum += input[i];
    }
    return false;
}
user_113850520
Related