Backtracking and stack overflow

Intuition:

We can abstract all the operations to a Tree, then apply DFS on it.

For example: startValue=2, target=3, the tree looks like:

/*
		  2
		 /\
		/  \
	   /    \
   1(-1)    4(x2)
	/\        /\--+
   /  \      /     \
0(-1) 2(x2) 3(-1)  8(x2)

*/

class Solution {
public:
	int brokenCalc(int startValue, int target) {
		unordered_set<int> visited;
		return backtracking(0, startValue, target, visited);
	}

	int backtracking(int count, int val, int target, unordered_set<int> & visited) {
		if (val == target) {
			return count;
		}
		if (visited.find(val) != visited.end()) {
			return -1;
		}
		int left = -1, right = -1;
		count++;
		visited.insert(val);
		if (val > 0) {
			left = backtracking(count, val - 1, target, visited);
		}
		if (val <= target * 2) {
			right = backtracking(count, val * 2, target, visited);
		}
		visited.erase(val);

		if (left != -1 && right != -1) {
			return min(left, right);
		} else if (left != -1) {
			return left;
		}
		return right;
	}
};

Change target to startValue

class Solution {
public:
	int brokenCalc(int startValue, int target) {
		int r = 0;
		while (target > startValue) {
			target = target % 2 > 0 ? target + 1 : target / 2;
			r++;
		}
		return r + startValue - target;
	}
};