Big O and Backtracking

SOLUTION 1
bool canMakeSumHelper(Vector<int>& v, int target, int sumSoFar) {
	if (v.isEmpty()) {
		return sumSoFar == target;
	}
	/* Here we choose the last element in the vector.
	 * We could have chosen any element, but the last
	 * is the easiest and fastest method.
	 */
	int choice = v[v.size() - 1];
	v.remove(v.size() - 1);

	bool with = canMakeSumHelper(v, target, sumSoFar + choice);
	bool without = canMakeSumHelper(v, target, sumSoFar);

	// And then we unchoose, by adding this back!
	v.add(choice);

	return with || without;
}

bool canMakeSum(Vector<int>& v, int target) {
	return canMakeSumHelper(v, target, 0);
}

SOLUTION 2
/*
 * This solution is similar to the one above, except it uses 
 * an additional index parameter in a vector to make the choices, 
 * instead of removing from the vector like solution 1 did.
 */
bool canMakeSumHelper(Vector<int>& v, int target, int sumSoFar, int index) {
	if (index >= v.size()) {
		return sumSoFar == target;
	}

	// This is our choice now. Remember we can choose any element
	// in the vector, so we choose the element at 'index'
	int choice = v[index];

	bool with = canMakeSumHelper(v, target, sumSoFar + choice, index + 1);
	bool without = canMakeSumHelper(v, target, sumSoFar, index + 1);
	
	// We don't have to add back, because we never removed!
	return with || without;
}

bool canMakeSum(Vector<int>& v, int target) {
	return canMakeSumHelper(v, target, 0, 0);
}

SOLUTION 3
bool canMakeSumHelper(Vector<int>& v, int target, int sumSoFar) {
    // We are only looking for one sum. If we already have a sum that matches
    // the target, there's no need to explore all the subsets (i.e, get to the
    // case when the underlying vector is empty). We can stop early!
    // Please note that this doesn't apply to all subset generation problems. The 
    // only reason we can do this is because we are looking for just one sum!
    if (sumSoFar == target) {
        return true;
    }
    
    if (v.isEmpty()) {
        // I'm leaving this to preserve the code from Solution 1.
        // But returning false here yields the correct results too! 
        // Do you see why ?
        return sumSoFar == target;
    }

    /* Here we choose the last element in the vector.
     * We could have chosen any element, but the last
     * is the easiest and fastest method.
     */
    int choice = v[v.size() - 1];
    v.remove(v.size() - 1);

    bool with = canMakeSumHelper(v, target, sumSoFar + choice);
    // We are only looking for one sum. If we can make the sum in the 
    // 'with' case, there's no need to try exploring the 'without' case
    if (with) { 
        // restore the underlying vector before returning. This is not 
        // needed for correctness, but the vector is passed by reference
        // to this recursive function. So it will be very bad to remove
        // some elements from it permanently.
        v.add(choice);
        return true;
    }
    
    bool without = canMakeSumHelper(v, target, sumSoFar);
    // And then we unchoose, by adding this back!
    v.add(choice);

    // I'm leaving this to preserve the code from Solution 1.
    // But returning 'without' here yields the correct results too! 
    // Do you see why ?
    return with || without;
}

string shrinkWord(string input, Lexicon& lex) {
	// We can't further shrink an empty word.
	// Also, if current word we have now is not
	// an English word(i.e. it isn't contained in 
	// the lexicon), that's also invalid(from the problem
	// description. )
    if (input.empty() || !lex.contains(input)) {
        return "";
    }

    string shortestWord = input;
    for (size_t i = 0; i < input.length(); i ++) {
		// Remove the letter at index i and recurse!
        string subword = input.substr(0, i) + input.substr(i + 1);
        string result = shrinkWord(subword, lex);

		// Compare the words we've generated so far to 
		// our shortestWord. If our new word is smaller, 
		// we have to change our shortestWord!
		// We need a special check for the empty string
		// because our base case returns "" for invalid inputs.
        if (!result.empty() && result.length() < shortestWord.length()) {
            shortestWord = result;
        }
    }
    return shortestWord;
}