# C++ Backtracking method Is my code not backtracking? Why isn’t it coming out 4 6 or 2 2 6? And still a mistake?

Asked by: Angela Wright 189 views IT

The topic is a subset of the backtracking method and the problem

Code:

#include<iostream>

using namespace std;

int a[1001];

int b[1001];

int x[1001];

int nsum;

Int n, c;

int k;

void subsetsum(int t){

if( t > n ){

if(nsum == c){

k = 1;

return;

}

}

else {

if(nsum + a[t] <= c) {

nsum += a[t];

x[t] = 1;

subsetsum(t + 1 );

nsum -= a[t];

}

if(nsum + a[t] > c){

x[t] = 0;

subsetsum(t+1);

}

}

}

int main(){

cin >> n >> c;

For(int i=1; i<=n; i++){

cin >> a[i];

b[i] = a[i];

}

subsetsum(1);

if(k == 1){

for(int i=1; i<=n; i++){

if(x[i] == 1 ) cout << b[i] << " ";

}

}

Else cout < < "No Solution!" << endl;

return 0;

}

+1

Votesv[j]=1;backtrack(i+1,total+c[i][j]);v[j]=0;//What does this step mean? The role of v[j] should be to record whether the jth job is assigned. v[j]=0 means that it is not assigned. Your topic is best solved using dynamic programming, see the backpacking question.

Ward- January 9, 2019 |