子集和求解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[]) {

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

--(1)-->    noOfSolutions += 1;

--(4)-->    return noOfSolutions;

    }

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

--(2)-->    A[i] = A[i]+1;

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

--(3)-->    A[i] = A[i]-1;

    return noOfSolutions;

}

例子

public static void main(String[] args) {

    System.out.println(subSetSum(0, 4, new int[3]));

}

输出

0 + 0 + 4

0 + 1 + 3

0 + 2 + 2

0 + 3 + 1

0 + 4 + 0

1 + 0 + 3

1 + 1 + 2

1 + 2 + 1

1 + 3 + 0

2 + 0 + 2

2 + 1 + 1

2 + 2 + 0

3 + 0 + 1

3 + 1 + 0

4 + 0 + 0

15