java - 使用递归(java)查找给定数字是否是给定集合(允许重复)的总和

Question

我试图找出给定数字是否是给定集合的总和， 例如:数字 12 是集合 s{3,2} 的总和， 因为:

3+3+3+3=12
or
2+2+2+2+2+2=12

但是 14 不是 s{8,10} 的总和，因为你不能用 创建数字 14 s 的总和。 我正在尝试仅使用递归而不使用循环在 java 中编写代码。 这是代码:

   public static boolean isSumOf(int[]s,int n)
   {
     return isSumOf(s,n,0,0,0);
   }


   private static boolean isSumOf(int[]s,int n,int i,int sum,int m)
   {
       boolean with=false;
       boolean without=false;

       if(i==s.length)
        return false;

       if(sum==n)   
        return true;

       if(m<=n)
        {
            with=isSumOf(s,n,i,sum+s[i]*m,m++);
            without=isSumOf(s,n,i,sum,m++);            
        }
       else
        {
            i=i++;
            m=0;
            isSumOf(s,n,i,sum,m);
        }

       return (with||without); 

   }

代码编译正常，但在运行测试时出现 stackOverFlowError。 这是测试代码:

  public static void main(String[]args)
  {  
      int[]a={18,10,6};
      int x=18+10+6;
      System.out.println(Ex14.isSumOf(a,x));
  }

请帮忙!!!

Answer 1

这看起来很糟糕:

with=isSumOf(s,n,i,sum+s[i]*m,m++);
without=isSumOf(s,n,i,sum,m++);

使用

with=isSumOf(s,n,i,sum+s[i]*m,++m);
without=isSumOf(s,n,i,sum,++m);

如果你想在被调用的方法中有一个更高的m。

除此之外，由于变量命名不当，我不知道代码做了什么。

还有这一行:

i=i++;

没有效果，如果要增加 i，请将其替换为以下内容之一:

i++;
i += 1;
i = i + 1;
i = ++i;

如果你不使用调用的结果

isSumOf(s,n,i,sum,m); 

调用它没有意义。