Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the

frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

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.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

• 1 <= candidates.length <= 30

• 2 <= candidates[i] <= 40

• All elements of candidates are distinct.

• 1 <= target <= 40

public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target)
    {
        IList<IList<int>> ans = new List<IList<int>>();
        FindSum(candidates, target, 0, new Stack<int>(), ans);

        return ans;
    }
    void FindSum(int[] nums, int target, int index, Stack<int> temp, IList<IList<int>> ans)
    {
        if (index == nums.Length)
        {
            if (target == 0)
            {
                ans.Add(temp.ToList());
                return;
            }
            return;
        }

        if (nums[index] <= target)
        {
            temp.Push(nums[index]);
            FindSum(nums, target - nums[index], index, temp, ans);
            temp.Pop();
        }
        FindSum(nums, target, index + 1, temp, ans);
    }
}

The given algorithm is a recursive solution to find all combinations of numbers that sum up to a target. It uses a depth-first search (DFS) approach to explore all possible combinations.

Time Complexity: The time complexity of this algorithm is O(N^(T/M)) where:

• N is the number of candidates,

• T is the target value, and

• M is the minimal value among the candidates.

The reasoning behind this is that in the worst-case scenario, the algorithm explores all possible combinations of the candidates to reach the target. Since each recursive step decreases the target by at least M (the smallest candidate), there can be at most T/M nested calls. For each of these calls, we explore N different branches (since there are N candidates), hence the N^(T/M) time complexity.

Space Complexity: The space complexity of this algorithm is O(T/M) which is the maximum depth of the recursion (i.e., the size of the call stack). This is because in the worst-case scenario, the target is decreased by the smallest candidate M at each step, so the maximum depth of the recursion is T/M.

Please note that these complexities are approximate and actual performance can vary depending on the specifics of the input and the runtime environment. Also, these complexities assume that the List.Add and Stack.Push/Pop operations are O(1), which is generally the case in most environments but could vary. If these operations are not O(1), the time and space complexity could be higher.