给定一个整数数组和一个目标值，任务是找出是否存在一个子集使得其元素之和等于目标值。

Question

这是我编写的函数。

    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)  ;
        }

这段代码完全正常。但是只要我将代码的最后一行改成这样。

    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])  ;
        }

超出了时间限制。如果改变顺序，对执行时间有什么影响我无法理解。请帮忙。

- Vivek kumar

---

你能给我们提供一下你所尝试的输入样本吗？ - Ismail

子集是否连续？ - Ryan

Answer 1

注意，|| 是短路的，即在 a || b 中，如果 a 为 true，则不会对 b 进行求值。

|| 的两个操作数之间的区别是，existsSum(arr, n-1, sum-arr[n-1]) “将”当前项添加到总和为总和的项目列表中，而existsSum(arr, n-1, sum)没有。

在第一个代码片段中，如果 existsSum(arr, n-1, sum-arr[n-1]) 为 true，则甚至不会调用 existsSum(arr, n-1, sum)。想象一下使用数组 [1,2,3] 和总和6调用此方法。每个递归调用的第一个操作数都将返回 true，因此无需评估第二个操作数。

类似地，在第二个代码片段中，首先运行 existsSum(arr, n-1, sum)，如果为 true，则不会调用 existsSum(arr, n-1, sum-arr[n-1])。但是，existsSum(arr, n-1, sum) 很少能够单独返回 true。我的意思是，对于调用 existsSum(arr, n-1, sum) 来返回 true，必须从对 existsSum(arr, n-1, sum-arr[n-1]) 的递归调用中得到值 true。通过分析不同的分支，您可以验证这一点（返回 true 的两个分支是 sum==0 和 arr[n-1] == sum。希望您会同意两者都很罕见）。这意味着回溯（即调用 existsSum(arr, n-1, sum-arr[n-1])）将绝对发生在existsSum(arr, n-1, sum) 中。

---

但最坏情况下，这两个代码片段是相同的。

- Sweeper

---

简而言之，测试用例很弱，两个解决方案都应该超时。 - Raj

Answer 2

这应该是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;
}

- Ryan