CODEWITHSUNDEEP
javaalgorithmbacktrackingsubset-sum
Zachary
Zachary

Reputation: 259

Subset Sum Problem: Returning a Variant of the Required Subset

Problem description:

Given a list of integers and a target sum, we're required to return another list containing Booleans. This Boolean list represents the subset that we're looking for.

Example:

Input: list (3, 34, 4, 12, 5, 2), target = 9.

Output: (false, false, true, false, true, false) (since 4+5 = 9; notice that this solution is not unique, but the problem only asks for one arbitrary solution).

My attempt:

I started with writing a method that checks if a solution even exists:

boolean subsetSumRec(List<Integer> list, int i, int sum) { //i is the index of the last element in list
    if(sum==0){
        return true;
    } else if(i<0 || sum<0){
        return false;
    }
    boolean include = subsetSumRec(list,i-1,sum-list.get(n));
    boolean exclude = subsetSumRec(list,i-1,sum);
    return include || exclude;
}

I made a new ArrayList (type: Boolean) resultList, that will be the output. My plan was to update resultList within the method subsetSumRec. It would be something like:

private boolean subsetSumRec(List<Integer> list, int i, int sum) {
    if(sum==0){
        return true;
    } else if(list.size()<=0 || sum<0){
        return false;
    }
    res.add(true);
    boolean include = subsetSumRec(list,i-1,sum-list.get(i));
    boolean exclude;
    if(include == false){
        res.remove(true);
        res.add(false);
        exclude = subsetSumRec(list, i - 1, sum);
    }
    return include || exclude;
}

This does not give the required result, but I don't see what's going wrong. How can this be optimized?

If updating resultList within subsetSumRec is not an option, then I'd have to get rid of the method that checks if there is a solution and use a backtracking algorithm (no dynamic programming!). I don't know how to start with the last one. Could somebody give me hint as to how to approach a backtracking algorithm for this problem (pseudocode?).

Thanks in advance.

Upvotes: 1

Views: 144

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Here's one example recursion in JavaScript. We return the second list if the solution is feasible, otherwise false.

function f(A, S, B=new Array(A.length).fill(false), i=A.length - 1){
  if (A[i] == S){
    B[i] = true
    return B
  }
    
  if (i == 0){
    if (A[i] == S){
      B[i] = true
      return B
    }
    return false
  }
  
  if (A[i] <= S){
    let maybeB = f(A, S - A[i], B, i - 1)
    if (maybeB){
      B[i] = true
      return B
    }
  }

  return f(A, S, B, i - 1)
}

var A = [3, 34, 4, 12, 5, 2]
var S = 9

console.log(JSON.stringify(A))
console.log(`Target: ${S}`)
console.log(JSON.stringify(f(A, S)))

S = 199
console.log(`\nTarget: ${S}`)
console.log(JSON.stringify(f(A, S)))

Upvotes: 1

Related Questions