> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/backtracking/combination-sum.md).

# 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:**

<pre><code><strong>Input: candidates = [2,3,6,7], target = 7
</strong><strong>Output: [[2,2,3],[7]]
</strong><strong>Explanation:
</strong>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.
</code></pre>

**Example 2:**

<pre><code><strong>Input: candidates = [2,3,5], target = 8
</strong><strong>Output: [[2,2,2,2],[2,3,3],[3,5]]
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: candidates = [2], target = 1
</strong><strong>Output: []
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= candidates.length <= 30`
* `2 <= candidates[i] <= 40`
* All elements of `candidates` are **distinct**.
* `1 <= target <= 40`

```csharp
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.