complexity.md

Time Complexity (Big O Time):

1. The program uses a recursive function, combinationSumRec, to generate combinations. In the worst case, it explores all possible combinations.

2. For each coin, it has two choices: either include the coin in the combination or exclude it. This results in a binary tree-like structure for the recursive calls, where each level of the tree represents a different coin and has two branches for including or excluding the coin.

3. In the worst case, the binary tree has a height of n (the number of coins). This means that the program makes 2^n recursive calls.

4. In each recursive call, the program performs constant-time operations to add or remove elements from the subList, which can be considered O(1).

5. Therefore, the overall time complexity is O(2^n), where n is the number of coins.

Space Complexity (Big O Space):

1. The space complexity of the program is determined by the space used for the call stack during the recursion and the space used for the subList and ans list.

2. The maximum depth of the recursion is n (the number of coins), which means the space used for the call stack is O(n).

3. The subList stores the current combination, and its size is bounded by the number of coins. In the worst case, it can have n elements.

4. The ans list stores all valid combinations, and its size is determined by the number of valid combinations. In the worst case, it can also have a size of 2^n, considering all possible combinations.

5. Therefore, the space complexity of the program is O(n + 2^n), where n is the number of coins.

In summary, the time complexity of the provided program is O(2^n), and the space complexity is O(n + 2^n), where n is the number of coins.