给出整数和和的数组,任务是查找给定数组的子集是否存在总和等于给定和的子集

这是我编写的功能。

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

超过时间限制。我不明白更改顺序对执行时间有什么影响。请帮助。

1
投票

注意||短路,即a || b,如果a为真,则不评估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,值true必须来自对existsSum(arr, n-1, sum-arr[n-1])的递归调用。您可以通过分析不同的分支来验证这一点。这意味着[existsSum(arr, n-1, sum)肯定会发生回溯

尽管在最坏的情况下,这两个代码段是相同的。