https://leetcode.com/problems/combination-sum/

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

합이 target이 되는 모든 경우의 수를 구한다.

void BT(int prevIndex, int target, vector<int>& candidates, vector<vector<int>>& output, vector<int>& input)
{
	if (target == 0)
		output.emplace_back(input);
	else if (target < 0) return;
	for (int i = prevIndex; i < candidates.size(); ++i)
	{
		int num = candidates[i];
		input.push_back(num);
		BT(i, target - num, candidates, output, input);
		input.pop_back();

	}
	
}

class Solution {
public:
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<vector<int>> output;
		vector<int> input;

		BT(0, target, candidates, output, input);
		return output;
	}
};

1, 2, 3 이 들어오고 5를 구한다 할 때,

1, 1, 1, 2 와 1, 1, 2, 1은 같은 것이다.

TREE의 노드를 구하는 공식은 각 레벨에서의 Branch 개수 k. 그리고 깊이 depth. 깊이에 +1

k^(depth+1)

tiem complexity 는 모든 노드의 개수. (기타 동작이 모두 O(1)으로 끝나기 때문)

각 level에서 최대 3개의 branch가 만들어진다.

depth = 5(구해야 할 값) / 1(최소값) 해서 최대 5.

T ≤ k^(5 + 1) 를 가진다.

항상 최대로 가지지 않으니까 이보다는 작을 것이다..!