子集和求解java

Question

recursion我需要使用和不使用任何循环编写代码，以找到K 是给定数字的backtracking方程的所有可能解。x1+x2+x3 = K和x1 , x2, x3之间是非零正整数1 - 10。

我的尝试：

public static int subSetSum(int i, int k, int A[]) {

    int sum = A[0] + A[1] + A[2];

    int noOfSolutions = 0;

    if(k - sum < 0 || i >= A.length)

        return 0;

    if(k - sum == 0) {

        System.out.println(A[0] + " + " + A[1] + " + " + A[2]);

        noOfSolutions =+ 1; }

    noOfSolutions = subSetSum(i+1,k,A);

    int newA[] = A;

    newA[i] = A[i]+1;

    noOfSolutions = subSetSum(i,k,newA);

    return noOfSolutions;

}

运行代码我只会得到一个解决方案。因此，如果尝试找到所有解决方案，6它只会打印出来1+1+4（0没有'解决方案）。

Answer 1

(1) 如果要添加和分配运算符是+=，而不是=+（这会将 +1 分配给 noOfSolutions）(2) 你不需要一个新的向量，它也将是相同的（A 和 newA 它将具有相同的内存地址，因此对其中一个的更改将影响它们两个）(3) 你应该在递归调用后恢复你的堆栈更改编辑(4) 解决后应停止public static int subSetSum(int i, int k, int A[]) {&nbsp; &nbsp; int sum = A[0] + A[1] + A[2];&nbsp; &nbsp; int noOfSolutions = 0;&nbsp; &nbsp; if(k - sum < 0 || i >= A.length)&nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; if(k - sum == 0) {&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(A[0] + " + " + A[1] + " + " + A[2]);--(1)-->&nbsp; &nbsp; noOfSolutions += 1;--(4)-->&nbsp; &nbsp; return noOfSolutions;&nbsp; &nbsp; }&nbsp; &nbsp; noOfSolutions += subSetSum(i+1,k,A);--(2)-->&nbsp; &nbsp; A[i] = A[i]+1;&nbsp; &nbsp; noOfSolutions += subSetSum(i,k,A);--(3)-->&nbsp; &nbsp; A[i] = A[i]-1;&nbsp; &nbsp; return noOfSolutions;}例子public static void main(String[] args) {&nbsp; &nbsp; System.out.println(subSetSum(0, 4, new int[3]));}输出0 + 0 + 40 + 1 + 30 + 2 + 20 + 3 + 10 + 4 + 01 + 0 + 31 + 1 + 21 + 2 + 11 + 3 + 02 + 0 + 22 + 1 + 12 + 2 + 03 + 0 + 13 + 1 + 04 + 0 + 015