Блог

Не мог бы кто-нибудь, пожалуйста, помочь мне с приведенным ниже кодом рекурсии?

Учитывая входной массив и цель, я хочу вернуть логическое значение true для любого непустого подмножества, которое суммируется с целевым значением. Я не понимаю, как вернуть правильное логическое значение из рекурсии.

В моем подходе ниже я суммирую все возможные комбинации непустого подмножества и хочу вернуть True вызывающей функции, если какое-либо из непустых подмножеств равно целевому значению. Проблема в том, что из-за нескольких стеков рекурсивных вызовов правильное / ожидаемое значение для логического значения для подмножества перезаписывается последующими / оставшимися стеками рекурсивных вызовов. Есть ли обходной путь для этой проблемы? Или мне использовать грубую силу? где я храню все возможные логические значения для каждой комбинации подмножеств в списке и возвращаю true, если хотя бы одно значение в списке является логическим True?

 public class RecursionPossibleToAchieveTargetSum {
    public static void main(String[] args ) {

        long[] arr = {4,8};
        long k = 4;  
        boolean flag = false;

        if (arr.length > 0 )
            flag = recursionHelper(arr,0,new long[arr.length],0, k);

        System.out.println(flag); 
    }

    public static Boolean recursionHelper(long[] arr, int spos, long[] temp, int tempIndex, long target) {
        if ( spos == arr.length ) {
            return (recursiveAddition(temp, temp.length - 1) == target);
        }

        recursionHelper(arr, spos   1, temp, tempIndex, target );
        temp[tempIndex] = arr[spos];
        return recursionHelper(arr, spos   1, temp, tempIndex   1, target);
    }

    public static long recursiveAddition(long[] arr, int spos) {
        if ( spos == 0 ) {
            return arr[spos];
        } else {
            return arr[spos]    recursiveAddition(arr, spos-1);
        }
    }
}
 

Вы можете использовать список <long[]>, чтобы сохранить все подмножества, которые в сумме составляют цель. Я также немного очистил рекурсию. Вы можете проверить размер этого списка результатов с помощью «result.size ()> 0» и вывести это логическое значение. Вы также можете распечатать каждый массив подмножеств, чтобы узнать, какие из них есть.

 import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;

public class RecursionPossibleToAchieveTargetSum {
    public static void main(String[] args ) {

        long[] arr = {1,2,4,1,3,5};
        long target = 8;
        List<long[]> result = new ArrayList<long[]>();

        if (arr.length > 0 ) {
            result = recursionHelper(arr, target);
        }
        System.out.println(result.size() > 0);
        for(long[] l : result) {
            System.out.println(Arrays.toString(l));
        }
    }

    public static List<long[]> recursionHelper(long[] arr, long target) {
        List<long[]> result = new ArrayList<long[]>();
        if (arr.length == 0) return resu<

        for(int j = arr.length; j > 0; --j) {
            long nextsom = recursiveAddition(Arrays.copyOfRange(arr, 0, j));
            if (nextsom == target) result.add(Arrays.copyOfRange(arr, 0, j));
        }
        result.addAll(recursionHelper(Arrays.copyOfRange(arr, 1, arr.length), target));
        return resu<
    }

    public static long recursiveAddition(long[] arr) {
        if ( arr.length == 1 ) return arr[0];
        return arr[0]    recursiveAddition(Arrays.copyOfRange(arr, 1, arr.length));
    }
}
 

Пример вывода с arr = {1,2,4,1,3,5} помощью и target = 8 :

 true
[1, 2, 4, 1]
[4, 1, 3]
[3, 5]