子集求和解java

Question

我需要使用 recursion 和 backtracking 编写代码并且不使用任何循环来找到方程 x1+x2+x3 = K 的所有可能解，其中 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) 你不需要一个新的 vector 而且它是相同的（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]));
}

输出

子集求和解java

Sub set sum solution java

java

recursion

backtracking