remove elements from link list whose sum equals to zero

Question

Given a list in form of linked list, I have to canceled out all the resources whose sum up to 0(Zero) and return the remaining list.

Like

6 -6 3 2 -5 4 returns 4
8 10 4 -1 -3 return 8 10

I only need algorithm to solve this question.

Answer 1

this is actually the classic subset sum problem which is NP-complete

see on wiki or google it to see articles about that

Answer 2

The following function just prints the nodes except the ones which are canceled out, you can make it push to a new list and return.

void printExCancel( node* head )
{
    node* start = head;
    node* end;

    while ( start )
    {
        bool mod = false;
        int sum = 0;
        end = start;
        while ( end )
        {
            sum += end->data;
            if ( sum == 0 )
            {
                start = end;
                mod = true;
                break;
            }
            end = end->next;
        }
        if ( mod == false ) {
            //push to new list
            printf( "%d\n", start->data );
        }
        //else {
        //    call funtion to delete from start to end
        //}
        start = start->next;
    }
}