Решение проблемы суммы подмножеств с использованием рекурсивных связанных структур

Question

Представьте неупорядоченную структуру с сингулярной связью с целочисленными узлами (например, 5 -> 8 -> 10 -> 2 -> 7) и заданной суммой (например, 15). Как я могу найти первое подмножество, рекурсивно равное сумме? В этом примере ответом будет 5 -> 8 -> 2 (5 -> 10 или 8 -> 7 также будет ответом, но не первым). У меня есть метод "узел f (узел, сумма)":

if node == null
   return null
else if node.value <= target
   return new Node(node.item, f(node.next, sum - node.value)
else
   return f(node.next, sum)

Однако, это вернет подмножества, которые меньше или равны сумме, а не точно сумма. Как я могу создать точный алгоритм?

Answer 1

Backtrack - это то, что вы ищете. :)

Также вы не определили порядок упорядочения подмножеств. В зависимости от этого возврата и остановки, когда вы обнаружите, что решение может не сработать, вам придется реализовать BFS для возможных решений.

Answer 2

Надеюсь, что справка по реализации ниже.

#include <stdio.h>
int N = 5;
int arr[] = {5,8,10,2,7};

bool dfs(int next, int sum)
{
    if(next==N) return false;
    if(sum==0) return true;  //backtrack to get first answer

    //include
    bool r1 = dfs(next+1, sum-arr[next]);

    //non-include
    bool r2 = dfs(next+1, sum);
    return r1||r2;
}

int main(void)
{
    printf("%d\n", dfs(0, 15));
    return 0;
}