Subset sum problem knapsack

[vld]

Условие:
Дана последовательность из N целых чисел. Найдите любую из ее подпоследовательностей, сумма элементов которой равна w, либо установите, что искомой подпоследовательности не существует.

Формат входного файла:
Во входном файле находятся числа N и w, а за ними следует последовательность из N целых чисел ai.
Формат выходного файла:
Если искомая подпоследовательность существует, выведите N чисел 0 или 1, разделенных пробелами. Единица на позиции i означает, что элемент последовательности ai принадлежит найденной подпоследовательности, 0 означает обратное. В противном случае выведите −1.
Ограничения:
1 ≤ N ≤ 40, 0 ≤ ai,w ≤ 10000000

Помогите исправить ошибку в восстановлении ответа.
Вот код:

Используется синтаксис C++

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <stdio.h>

using namespace std;

int n,w,i,j;

ofstream fo("output.txt");
ifstream fi("input.txt");

int main (){

        fi >> n >> w;   
        
        int* A = (int*)malloc(sizeof(int)*(n+1));
        int* B = (int*)malloc(sizeof(int)*(n+1));       
        int* S = (int*)malloc(sizeof(int)*(w+1));
        
        for (i = 1; i <= n; i ++)
                fi >> A[i];
        
        S[0] = 1;

        for (j = 1; j <= w; j ++)
                S[j] = 0;
                
                for (i = 1; i <= n; i ++){
                        for (j = w; j >= A[i]; --j){
                        S[j] |= S[j - A[i]];
                }
                
        }

        j = w;
        if(S[w]){
        for (i = n; i >= 1; i --){
                if (j > A[i]){          
                        B[i] = 1;
                        j -= A[i];
                } else {
                        B[i] = 0;
                }
        }
        for(i = 1; i <= n; i++)
                fo << B[i] << " ";
        } else {
                fo << -1;
        }
        
}
 

[venco]

При восстановлении первое попавшееся число брать нельзя. Надо при получении сумм записывать в S не 1, а индекс числа, которое привело к этой сумме. Потом использовать эти индексы.

[vld]

Извените, если не трудно, то напишите пожалуйста код

[venco]

Здесь так не принято.