Как исправить мой код, чтобы написать вариант решения проблемы SubSet Sum?

Question

Рассмотрим проблему суммы подмножеств (SUSU), мне нужно написать вариант решения, показанного в классе, который также выведет, какие веса суммируются для получения заданной суммы. Например, если:

sum=12;
int[] weights={1,7,9,3};

вывод будет: 0011 То есть для каждого значения в весах мы пишем «1», если оно было добавлено, или «0» в противном случае.

С помощью друга я написал следующий код:

    public static void main(String[] args) {

    int[] arr={9,1,7,3};
    System.out.println(Arrays.toString(SubsetSum(arr,12)));
}   

public static int[] SubsetSum(int[] arr, int sum){
    int[] output= new int[arr.length];
    return SubsetSum(arr,sum, 0, output);
}

public static int[] SubsetSum(int[] arr, int sum, int index, int[]weights){
    int[] output= new int[arr.length];
    if(sum==0)
        return weights;
    if(sum<0 | index>=arr.length)
        return output;
    weights[index]=0;
    int[] arr1= SubsetSum(arr,sum,index+1, weights);
    weights[index]=1;
    int[]arr2=SubsetSum(arr,sum-arr[index],index+1,weights);
    boolean isZero=true;
    for(int i=0; i<arr1.length & isZero; i=i+1)
        if(arr1[i]!=0)
            isZero=true;
    if(isZero)
        return arr2;
    else
        return arr1;
}

Я ожидаю, что выход SubsetSum (arr, 12) будет [1, 0, 0, 1], но фактический вывод - [0, 0, 0, 0]. Я понимаю, почему он возвращает этот вывод из моего кода, но я не знаю, как это исправить.

Answer 1

Я изменил способ возврата результата. Теперь используемые элементы кодируются в битах параметра used.

Ideone .

Основные печатает индексы предметов (или ничего в случае сбоя) - 1,2,3 для примера, например, 1 + 7 + 13

Я не знаком с Java, поэтому представьте результат для лучшего просмотра (возможно, что-то вроде inttobinary)

public static void main(String[] args) {

    int[] arr={9,1,7,13,3};
    int i = 0;
    int res = SubsetSum(arr, 21, 0, 0);
    while (res > 0) {
        if ((res & 1) > 0) 
            System.out.println(i);
        i++;
        res >>= 1;
    }       
}   

public static int SubsetSum(int[] arr, int sum, int index, int used){
    if(sum==0)
        return used;
    if(sum<0 | index>=arr.length)
        return 0;
       int a = SubsetSum(arr,sum,index+1, used);
       int b = SubsetSum(arr,sum-arr[index],index+1, used | (1 << index));
       if (a > 0)
          return a;
       else
          return b;
}  
}

P.S. Недостатки в вашем коде:
isZero никогда не меняется.
Если вы исправите логику, чтобы вернуть ненулевой массив, он будет заполнен всеми 1 - возможно, потому что weights[index]=1; изменяет тот же экземпляр массива через общую ссылку (не знаю терминологию Java). В моем коде на каждом уровне рекурсии есть собственный экземпляр used, и изменение его битов не влияет на значения в других ветвях.